# How find the closed $a_{n}$ form

let sequence $\{a_{n}\}$,such $a_{1}=0,a_{2}=2,a_{3}=5$,and for $n\in N^{+}$,such $$\begin{cases} a_{2n}=2n+2a_{n}\\ a_{2n+1}=2n+1+a_{n}+a_{n+1} \end{cases}$$ How can I find the closed form of $\{a_{n}\}$?

My try: we have

$$a_{2n+1}-a_{2n}=a_{n+1}-a_{n}+1$$ so if $n=2k$,then $$a_{2n+1}-a_{2n}=a_{n+1}-a_{n}+1$$ $$a_{2n}-a_{2n-1}=a_{n}-a_{n-1}+1$$ $\cdots\cdots\cdots$ $$a_{3}-a_{2}=a_{2}-a_{1}+1$$ so add all this equation,we have $$a_{2n+1}-a_{2}=a_{n+1}-a_{1}+(2n-1)$$ then $$a_{2n+1}=a_{n+1}+2n+1$$ My idea is true? and How solve this problem,and this This problem background is china comption today

• What is "china comption today"? – GEdgar Nov 6 '13 at 18:49
• "A competition that was held today in China". @GEdgar – zyx Nov 12 '13 at 5:36

By calculating the first few dozen values by hand, one notices the pattern that $$a_{n+1} = a_n + (k+2) \quad\text{for all } 2^k \le n < 2^{k+1}.$$ This is quickly verified by induction on $k$ from the original recursion; for example, $$a_{2n+1}-a_{2n} = (2n+1+a_n+a_{n+1}) - (2n+2a_n) = 1 + (a_{n+1}-a_n).$$ From here, it is not hard to prove by induction that $a_{2^k} = k2^k$ for all $k\ge0$; combining these "landmark" values with the new pattern above will provide a closed form for every $a_n$.

Take care, if I had one more line, you'll see that we cannot sum like you did :

$$a_{2n+1}-a_{2n}=a_{n+1}-a_{n}+1$$ $$a_{2n}-a_{2n-1}=a_{n}-a_{n-1}+1$$ $$a_{2n-1}-a_{2n-2}=a_{n}-a_{n-1}+1$$ and not $$a_{2n-1}-a_{2n-2}= a_{n-1}-a_{n-2}+1$$ $\cdots\cdots\cdots$ $$a_{3}-a_{2}=a_{2}-a_{1}+1$$

And the equation you end up with is $a_{2n+1}=2n+1+a_{n}+a_{n+1}$, which unfortunately is something you already knew.

• Why a downvote? He asks if his idea is true, I explain why it's false. If I'm wrong please explain... – gvo Oct 30 '13 at 17:35

Here is a closed form formula for $a_n$
$$a_n = (\lfloor \log_2{n}\rfloor + 2)n - 2^{\lfloor \log_2{n}\rfloor +1}$$ To get this simply notice that $$a_n = n + a_{\lfloor \frac{n}{2}\rfloor}+ a_{\lceil\frac{n}{2}\rceil}$$ Then follow Greg Martin's sugestions.

• These are logarithms to base 2? – Greg Martin Nov 13 '13 at 21:50