Expert: Abe Mantell - 8/14/2011

Question
1. Prove the formula:

0(2)^0 + 1(2)^1 + ... + n(2)^n = (n-1)[2^(n+1)] + 2

for all integers n>=0

2. Use induction to prove:

(0^2)(2^0) + (1^2)(2^1) + ... + (n^2)(2^n) = f(n)[2^(n+1)] + d

for all integers n>=0

(Here d is a constant, and f(n) is a certain quadratic polynomial in n. First, by substituting small values for n and by assuming a formula of the form above is true, find the only possibilities for f(n) and d. Then use induction to prove the formula for that specific polynomial f(n) and constant d.)

Answer
1. Proof by Induction: sum(k*2^k, k from 0 to n)
I. Show true for n=0
.. 0*2^0=0 and (0-1)*2^(0+1)+2=-1(2)+2=0 check!
II. Assume true for n=m, m>=0
.. sum(k*2^k, k from 0 to m)=(m-1)*2^(m+1)+2
III. Show true for n=m+1
.. sum(k*2^k, k from 0 to m+1)=sum(k*2^k, k from 0 to m)+(m+1)*2^(m+1)
.. = (m-1)*2^(m+1)+2 + (m+1)*2^(m+1)
.. = (m-1)*2^(m+1)+(m+1)*2^(m+1)+2
.. = [(m-1)+(m+1)]*2^(m+1)+2
.. = 2m*2^(m+1)+2
.. = m*2^(m+2)+2  QED

2. After a few trials, we can see the formula looks like: (n^2-2n+3)*2^(n+1)-6

Now use Induction to prove it (goes like the previous problem).

Abe