Subscribe via feed.

Alternating series

Posted by Chris on July 20, 2014 – 7:23 am

An increasing sequence of integers is said to be alternating if it starts with an odd term, the second term is even, the third term is odd, the fourth is even, and so on. The empty sequence (with no term at all!) is considered to be alternating.

Let A(n) denote the number of alternating sequences which only involve integers from the set {1, 2, . . . , n}. Show that A(1) = 2 and A(2) = 3. Find the value of A(10).

NB I originally asked for A(20).


This post is under “MathsChallenge” and has 13 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

13 Responds so far- Add one»

  1. 1. Karl Sharman Said:

    I am going with A(20) = 17711, as I think this is the Fibonacci sequencing.

    Not given it overly much thought, so I am probably wrong, and it is the end of the weekend, and I have to go to work tomorrow, so I shall follow it up later, once the monkeys are set off with their little tasks. And I’m not strictly sober.

  2. 2. Chris Said:

    A(20) is enormously larger than the way 8 snails can finish a race.

  3. 3. Chris Said:

    Sadly this seems too easy. I get A(20) = 14633180168457. Of course, if that’s wrong then I’ve goofed again.

    Having done the calcs, I’ve changed the question to ask for A(10). A(20) needs too many dull calculations. Of course it may be that there’s a slick trick that I haven’t spotted (or I’ve completely goofed). A(10) is numerically quite near to Karl’s first number.

  4. 4. Chris Said:

    I had goofed. The numbers are much larger than I thought. However, it’s still quite easy.

  5. 5. Karl Sharman Said:

    Here is what I scribbled down last night – I have written in capitals the area where my correct interpretation of the question does not match the incorrect phrasing of the question that I was answering. ;-) I feel that had you phrased the question, as per my answer, I would have been right. D’oh – Twice this month I have not read the question correctly!

    n = 1, A(1) = 2, namely the sequences {}(empty) and {1}
    n = 2, A(2) = 3 : {},{1},{1,2}

    A(1), A(2), A(3),… is the Fibonacci series starting with 2! thus, A(20) = fib(22) = 17711

    A(n) = fib(n+2)
    A(n+1) = A(n) + A(n-1)

    A’(n) : the number of alternating sequences which involve only integers from the set {1,2,….,n} with the LENGTH of the sequence being ODD

    A”(n) : the number of alternating sequences which involve only integers from the set {1,2,….,n} with the LENGTH of the sequence being EVEN
    We have A(n) = A’(n)+A”(n)

  6. 6. Chris Said:

    I misread it too, and so only used the lowest integers for the subsets. I found a nice-ish identity though: e.g. 10! 10! + 10! 9! = 11! 9!

    Here’s my latest interpretation of the question. For {1,2,3} we have:
    {1,2,3}, {3,2,1}, {1,2}, {3,2}, {1},{3}, {} => A(3) = 7

    So the good news is that the problem isn’t as easy as I first thought. I’m sure it’s easier than the Hi-Lo-Hi-Lo problem though.

  7. 7. slavy Said:

    If I’m interpreting the problem correctly, then it’s quite easy. However, A(3) should be 5, since two of the sequences above are decreasing, which is not allowed

  8. 8. Chris Said:

    Don’t you wish! The question doesn’t say anything about increasing or decreasing, only odd or even.

    The nastiest part is that there can be one more odd than even. It makes the equations a royal pain.

  9. 9. slavy Said:

    “An increasing sequence of integers is said to be alternating…” – I’m not wishing, just reading :) And, I had 5 min to wrote it down now and back up Karl with the Fibonacci sequence and the answer.

  10. 10. Chris Said:

    I think A(10) = 55731 and A(20) = 50 963 818 537 911.

    If that’s right, the problem is easy. It’s just a bit boring to number crunch.

  11. 11. Chris Said:

    Here are the values of A(n) for n = 0 to 14:
    1,2,3,7,15,46,139,557,2229,11146,55731,334387,2006323,14044262,98309835

    Of course that assumes my maths is correct. Is there a mathematician in the house?

  12. 12. Zorglub Said:

    As Slavy has pointed out: what happened to the word ‘increasing’ ?

    A(3) = 5 and not 7

  13. 13. Chris Said:

    OMG. Thank you. Slavy’s comment went straight over my head (I focused on the alternating, not the increasing). I guess I meanwhile took the increasing bit to apply to the initial set.

    On the bright side, that means I have another problem to solve. Even better, I fancy it is harder :)

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0