# Sum $\sum_{k=0}^{2013}2^ka_{k}$

let real sequence $a_{0},a_{1},a_{2},\cdots,a_{n}$,such $$a_{0}=2013,a_{n}=-\dfrac{2013}{n}\sum_{k=0}^{n-1}a_{k},n\ge 1$$

How find this sum $$\sum_{k=0}^{2013}2^ka_{k}$$

My idea: since $$-na_{n}=2013(a_{0}+a_{1}+a_{2}+\cdots+a_{n-1})\cdots\cdots(1)$$ so $$-(n+1)a_{n+1}=2013(a_{0}+a_{1}+\cdots+a_{n})\cdots\cdots (2)$$ then $(2)-(1)$,we have $$na_{n}-(n+1)a_{n+1}=2013a_{n}$$ then $$(n+1)a_{n+1}=(2013-n)a_{n}$$ then $$\dfrac{a_{n+1}}{a_{n}}=\dfrac{2013-n}{n+1}$$ so $$\dfrac{a_{n}}{a_{n-1}}\cdot\dfrac{a_{n-1}}{a_{n-2}}\cdots\dfrac{a_{1}}{a_{0}}=\cdots$$ so $$\dfrac{a_{2013}}{a_{0}}=\dfrac{1}{2013}\cdot\dfrac{2}{2012}\cdots\dfrac{2013}{1}=1?$$ then How can find this sum?

Method 1 (generating function)

Let $a(z) = \sum\limits_{k=0}^\infty a_k z^k$, notice

$$a(z)\left(\frac{z}{1-z}\right) = \left(\sum_{k=0}^\infty a_k\right)\left( \sum_{\ell=1}^\infty z^\ell\right) = \sum_{n=1}^\infty\left(\sum_{k=0}^{n-1}a_k\right)z^n$$

and $$\left(z\frac{d}{dz}\right)a(z) = \left(z\frac{d}{dz}\right)\sum_{n=0}^\infty a_nz^n = \sum_{n=1}^\infty na_n z^n$$ The equality $a_{n}=-\dfrac{2013}{n}\sum_{k=0}^{n-1}a_{k},\,n\ge 1$ implies

$$\frac{da(z)}{dz} = -2013\frac{a(z)}{1-z} \quad\iff\quad \frac{d}{dz} \log a(z) = 2013\frac{d}{dz}\log(1-z)$$

and hence $$a(z) = a_0(1-z)^{2013} = 2013(1-z)^{2013}$$

Since this is a polynomial with degree 2013, we get

$$\sum_{k=0}^{2013} a_k 2^k = a(2) = 2013 (1-2)^{2013} = -2013$$

Method 2 (more elementary, appropriate for middle school students)

Let $b_n = \sum\limits_{k=0}^n a_k$, we have $b_0 = 2013$ and for $n > 0$, $$n(b_n-b_{n-1}) = -2013 b_{n-1}\quad\iff\quad b_n = -\frac{2013 -n}{n}b_{n-1}$$ This implies $$b_n = (-1)^n \frac{\prod\limits_{k=1}^n (2013-k)}{n!} b_0 = (-1)^n \frac{2013!}{n!(2013-n-1)!} = (-1)^n \binom{2013}{n} (2013-n)$$

Notice $$b_{n-1} = (-1)^{n-1}\frac{2013!}{(n-1)!(2013-n)!} = (-)^{n-1} \binom{2013}{n} n,$$ we obtain

$$a_n = b_n - b_{n-1} = (-1)^n 2013\binom{2013}{n}$$

Using binomial theorem, we can evaluate the desired sum as

$$\sum_{k=0}^{2013} a_k 2^k = 2013 \sum_{k=0}^{2013} \binom{2013}{k}(-2)^k = 2013 (1-2)^{2013} = -2013$$

• It's nice methods! Thank you,+1 because this problem is middle school student problem,I think have other methods – math110 Jan 28 '14 at 10:33
• @math110 In your question, you should mention this is a problem for middle school students. In any event, I have cooked up an alternate solution that is more elementary and should be doable by middle school students. – achille hui Jan 28 '14 at 13:55
• oh,Nice! Thank you very much – math110 Jan 28 '14 at 14:35

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{a_{0}=2013\,,\quad a_{n} = -\,{2013 \over n}\sum_{k = 0}^{n - 1}a_{k}\,,\quad n \geq 1:\ {\large ?}}$

\begin{align} &\pars{n + 1}a_{n + 1} - na_{n}=-2013\pars{\sum_{k = 0}^{n}a_{k} - \sum_{k = 0}^{n - 1}a_{k}} = -2013 a_{n} \\[3mm]&\imp\quad \pars{n + 1}a_{n + 1} - \pars{n - a_{0}}a_{n} = 0 \end{align}

\begin{align} &\sum_{n = 0}^{\infty}\pars{n + 1}a_{n + 1}z^{n} - \sum_{n = 0}^{\infty}na_{n}z^{n} +a_{0}\sum_{n = 0}^{\infty}a_{n}z^{n}=0 \\[3mm]& \sum_{n = 1}^{\infty}na_{n}z^{n - 1} -z\partiald{}{z}\sum_{n = 0}^{\infty}a_{n}z^{n} +a_{0}\sum_{n = 0}^{\infty}a_{n}z^{n}=0 \\[3mm]& \partiald{}{z}\sum_{n = 0}^{\infty}a_{n}z^{n} -z\partiald{}{z}\sum_{n = 0}^{\infty}a_{n}z^{n} +a_{0}\sum_{n = 0}^{\infty}a_{n}z^{n}=0 \\[3mm]& \partiald{}{z}\sum_{n = 0}^{\infty}a_{n}z^{n} -{a_{0} \over z - 1}\sum_{n = 0}^{\infty}a_{n}z^{n}=0 \\[3mm]& \pars{z - 1}^{-a_{0}}\partiald{}{z}\sum_{n = 0}^{\infty}a_{n}z^{n} -a_{0}\pars{z - 1}^{-a_{0} - 1}\sum_{n = 0}^{\infty}a_{n}z^{n}=0 \\[3mm]& \partiald{}{z} \bracks{\pars{z - 1}^{-a_{0}}\sum_{n = 0}^{\infty}a_{n}z^{n}}=0 \quad\imp\quad\pars{z - 1}^{-a_{0}}\sum_{n = 0}^{\infty}a_{n}z^{n} = -a_{0} \end{align}

\begin{align} &\sum_{n = 0}^{\infty}a_{n}z^{n}=a_{0}\pars{1 - z}^{a_{0}} =a_{0}\sum_{n = 0}^{a_{0}}{a_{0} \choose n}\pars{-1}^{n}z^{n} \end{align}

With $\ds{z = -2}$: $$\color{#00F}{\large\sum_{k = 0}^{2013}2^{k}a_{k}} = 2013\pars{1 - 2}^{2013} = \color{#00F}{\large -2013}$$

oh sorry, i omit some details !

by the symmetric property, $a_{0}=-a_{2013}$$,$$a_{1}=-a_{2012}$$,...... the hint is : (a_{2}+4/3a_{2}+......+4/3a_{3}+......)/(ta_{0})=-a_{1}/a_{0}(a_{1}-4/3a_{1}-......-4/3a_{2}-......) we assume that : t_{1}=\frac{(a_{2}+4/3a_{2}+......+4/3a_{3}+......)}{(-a_{1}-4/3a_{1}-......-4/3a_{2}-......)} t_{2}=\frac{(a_{3}+4/3a_{3}+......+4/3a_{4}+......)}{(-a_{2}-4/3a_{2}-......-4/3a_{3}-......)} so, a_{0}(1+1+4/3+......-a_{0}-4/3a_{0}-......-4/3\cdot1/2(a_{0}+a_{1})-......)$$=$$(\frac{a_{0}}{a_{1}}\cdot{\frac{a_{1}}{a_{2}}}$$\cdot......\cdot{\frac{a_{2012}}{a_{2013}}})\cdot{\frac{a_{0}}{a_{2013}}}\cdot$$t_{1}\cdot{t_{2}}......\cdot{t_{n}}$$=t_{1}\cdot{t_{2}}......\cdot{t_{n}}$ $=\frac{(a_{n-1}+4/3a_{n-1}+......+4/3a_{n-2}+......)}{(-a_{1}-4/3a_{1}-......-4/3a_{2}-......)}=1$

you can write out the expression of $a_{n}$ and find its regular :

$a_{0}=a_{0}$

$a_{1}=-2013a_{0}$

$a_{2}=-\frac{2013}{2}(a_{0}+a_{1})$

$a_{3}=-\frac{2013}{3}(a_{0}+a_{1}+a_{2})$

$......$

$sum$$=a_{0}(1-2\cdot{2013}-4\cdot{\frac{2013}{2}}-8\cdot{\frac{2013}{3}}-......) +a_{1}(-4\cdot{\frac{2013}{2}}-8\cdot{\frac{2013}{3}}-......)$$+a_{2}(-8\cdot{\frac{2013}{3}}-......)+......$

then by the symmetric property :

$\Longrightarrow$$a_{0}(-2\cdot{2013}-4\cdot{\frac{2013}{2}}-8\cdot{\frac{2013}{3}}-......) +a_{1}(-4\cdot{\frac{2013}{2}}-8\cdot{\frac{2013}{3}}-......)$$+a_{2}(-8\cdot{\frac{2013}{3}}-......)+......$$=-2a_{0}((a_{0}+a_{0}+4/3a_{0}+......)$$+(a_{1}+4/3a_{1}+......)$$+4/3a_{2}+......)$$\Longrightarrow$$((a_{0}+a_{0}+4/3a_{0}+......)$$+(a_{1}+4/3a_{1}+......)$$+4/3a_{2}+......)$$=a_{0}(1+1+4/3+......-a_{0}-4/3a_{0}-......-4/3\cdot1/2(a_{0}+a_{1})-......)$

$=\frac{a_{0}}{a_{1}}\cdot$$(a_{1}+a_{1}+4/3a_{1}+......+a_{2}+4/3a_{2}+......)$$=$

$\frac{a_{0}}{a_{1}}\cdot{\frac{a_{1}}{a_{2}}}$$\cdot$$(a_{2}+a_{2}+4/3a_{2}+......+a_{3}+4/3a_{3}+......)$ $=\frac{a_{0}}{a_{1}}\cdot{\frac{a_{1}}{a_{2}}}$$\cdot......\cdot{\frac{a_{2012}}{a_{2013}}}=1 i add a supplement to this proof : ((a_{0}+a_{0}+4/3a_{0}+......)$$+(a_{1}+4/3a_{1}+......)$$+4/3a_{2}+......)$$=a_{0}(1+1+4/3+......-a_{0}-4/3a_{0}-......-4/3\cdot1/2(a_{0}+a_{1})-......)$$=a_{0}(1+4/3+......-4/3a_{0}-......-4/3\cdot1/2(a_{0}+a_{1})-......) =\frac{a_{0}}{a_{1}}\cdot{t_{1}}\cdot$$(a_{1}-a_{1}+4/3a_{1}+......+a_{2}+4/3a_{2}+......)$$= \frac{a_{0}}{a_{1}}{\frac{a_{1}}{a_{2}}}\cdot{t_{1}\cdot{t_{2}}}\cdot$$(4/3a_{2}-4/3a_{2}+......+a_{3}+4/3a_{3}+......)$

$=\frac{a_{0}}{a_{1}}\cdot{\frac{a_{1}}{a_{2}}}$$\cdot......\cdot{\frac{a_{2012}}{a_{2013}}}\cdot{t_{1}}\cdot{t_{2}}\cdot......\cdot{t_{n}}\cdot$$(4/3a_{1}+4/8a_{1}+......+8/4a_{2}+16/5a_{2}+......+16/5a_{3}+......)$

where, $t_{i}=\frac{a_{i}}{a_{0}}$

and we continue our procedure ,which deduce that :

$((a_{0}+a_{0}+4/3a_{0}+......)$$+(a_{1}+4/3a_{1}+......)$$+4/3a_{2}+......)$

$=\frac{a_{0}}{a_{1}}\cdot{\frac{a_{1}}{a_{2}}}$$\cdot......\cdot{\frac{a_{2012}}{a_{2013}}}\cdot{t_{1}}\cdot{t_{2}}\cdot......\cdot{t_{n}}$$=(-1)^2=1$

that is because if we can omit all $a_{0}$, then $a_{1}=a_{1}$

if we can omit all $a_{0}$ and $a_{1}$, then $a_{2}=\frac{3}{4}a_{2}$$\Longrightarrow$$\frac{4}{3}a_{2}=a_{2}$

......

so we can use $t_{i}$ to omit the one more surplus term in each step,so on, we can repeat our procedure and get our last result !