2
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ These are logarithms to base 2? $\endgroup$ – Greg Martin Nov 13 '13 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy