Prove that for every positive integer n, ∑ k2^k = (n-1)2^(n+1) + 2?

Prove that for every positive integer n, ∑(from k =1 to n) k2^k = (n-1)2^(n+1) + 2 by INDUCTION.

My first step was to prove the basis step:

P(1) = 1*2^1 = (1-1)2^(1+1) + 2 = 2.

I have trouble with the inductive step:

First we assume the inductive hypothesis.

We'd have to prove ∑ k2^k + (k+1)2^(k+1) = k*2^(k+2)+2

And now I'm lost... please help!

3 Answers

Relevance
  • Anonymous
    9 years ago
    Best answer

    Assume that it's true for n=j. Then:

    ∑ k (2^k) = (j-1) 2^(j+1) + 2

    where the sum goes from n = 1 to j. If we add (j+1) * 2^(j+1) to both sides, we get the sigma going from n=1 to j+1, and:

    ∑ k (2^k) = (j-1) 2^(j+1) + 2 + (j+1) * 2^(j+1)

    ∑ k (2^k) = j 2^(j+1) - 2^(j+1) + 2 + j*2^(j+1) + 2^(j+1)

    ∑ k (2^k) = j 2^(j+1) + j*2^(j+1) + 2

    ∑ k (2^k) = 2j 2^(j+1) + 2

    ∑ k (2^k) = j 2^(j+1 + 1) + 2

    ∑ k (2^k) = (j+1 - 1) 2^(j+1 +1) + 2

    So this proves that if it works for n=j, then it works for n=j+1 too.

  • 9 years ago

    I'll be starting from the inductive step.

    ∑ k2^k + (k+1)2^(k+1)

    : (k-1)2^(k+1) + 2 + (k+1)2^(k+1)

    : k 2^(k+1) - 2^(k+1) + 2 + k 2^(k+1) + 2^(k+1)

    : 2k 2^(k+1) + 2

    : k 2^(k+1 + 1) + 2

    : k 2^(k+2) + 2

    Hope this helps!!!!!

  • 9 years ago

    Step n is

    ∑ k2^k = (n-1)2^(n+1) + 2

    Step n+1 is

    ∑ k2^k + (n+1)2^(n+1)= (n-1)2^(n+1) + 2 + (n+1)2^(n+1)

    n+1

    ∑ k2^k = (n-1)2^(n+1) + 2 + (n+1)2^(n+1) = 2^(n+1)[n-1+n+1] +2 =2^(n+1)*2n +2 =

    1

    n2^(n+2) +2 QED

Still have questions? Get answers by asking now.