# 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 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 at 13:55
oh,Nice! Thank you very much –  math110 Jan 28 at 14:35