I am new to this forum so do correct me if I am doing anything wrong.
(Problem 6 of British Mathematics Olympiad1 - 1994)
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]$. Find the value of $A(20)$ and prove that your value is correct.
I believe a method is to set up a recursion.
What I have done is as follows:
(I've slightly changed the definition of A(n) to be the set of all possible sequences)
Let $O(n)$ be the number of increasing alternating sequences which only involve integers from the set $[1, 2, ..., n]$ that end in an odd number and $E(n)$ be the number of increasing alternating sequences which only involve integers from the set $[1, 2, ..., n]$ that end in an even number.
For every even $n$, $O(n+2) = O(n)+E(n)+1$.
Proof: For every sequence that ends in an odd number in $A(n)$, it will also be a sequence of $A(n+2)$, hence add $O(n)$. For every sequence that ends in an even number in $A(n)$, $n+1$, which is odd, can be added to the end of that sequence, hence add $E(n)$. The sequence with only $n+1$ also satisfies the conditions hence add $1$.
For every even $n$, $E(n+2)=2E(n)+O(n)+1$.
Proof: For every sequence that ends in an odd number in $A(n)$, $n+2$, which is even, can be added to the end of that sequence, hence add $O(n)$. For every sequence that ends in an even number in $A(n)$, nothing or both $n+1$ and $n+2$ can be added to the end of that sequence, hence add $2E(n)$. The sequence with only $n+2$ also satisfies the conditions hence add $1$.
$A(n) = E(n)+O(n)+1$
Proof: Every sequence either ends in an even number or an odd number or is an empty sequence.
Starting with $E(0)=0$ and $O(0)=0$, we get $E(20)=10945$ and $O(20)=6765$, meaning $A(20)=17711$.
Is there anything wrong with my method? If not is there a more efficient way to get to the answer? Thanks.
If a sequence starts with 1, the rest of the sequence can be found by adding 1 every term of a sequence from $A(n-1)$.
If it doesn't begin with 1, you get it by adding 2 to every term of a sequence from $A(n-2)$.
So $A(n)=A(n-1)+A(n-2)$.