## 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).

July 20th, 2014 at 3:08 pm

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.

July 20th, 2014 at 5:13 pm

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

July 20th, 2014 at 5:40 pm

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.

July 20th, 2014 at 6:30 pm

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

July 21st, 2014 at 12:16 am

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)

July 21st, 2014 at 3:16 am

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.

July 21st, 2014 at 11:04 am

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

July 21st, 2014 at 11:18 am

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.

July 21st, 2014 at 11:24 am

“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.

July 22nd, 2014 at 2:18 pm

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.

July 23rd, 2014 at 6:53 am

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?

July 23rd, 2014 at 8:44 am

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

A(3) = 5 and not 7

July 23rd, 2014 at 11:02 am

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