3
$\begingroup$

I'm trying to apply an induction proof to show that $((n+1) 2^n - 1 $ is the sum of $(i 2^{i-1})$ from $0$ to $n$.

  • the base case: L.H.S = R.H.S
  • we assume that $(k+1) 2^k - 1 $ is true.
  • we need to prove that $(k+2) 2^{k+1} - 1$

My try to prove 3 is as follows:

$(k+2) 2^{k+1} - 1$

$(k+2) (2^k * 2) - 1$ , from 2: $2^k = 1/(k+1)$

$(k+2) (2 / (k+1)) - 1$

$(k+1) 2 - 1$

My question is, how could I get to $2^k$ from the last line to prove this formula is right?

$\endgroup$
3
$\begingroup$

You have a typo in your statement. You want to show $$ \sum_{i=0}^n i 2^{i-1} = n 2^n - 2^n + 1 $$

Base case $n = 0$:

$$ \sum_{i=0}^0 i 2^{i-1} = 0 = 0 - 1 + 1$$

Assume that $$ \sum_{i=0}^n i 2^{i-1} = n 2^n - 2^n + 1$$

Then make an induction step from $n$ to $n+1$. This means you want to show that given your assumption you can show

$$ \sum_{i=0}^{n+1} i 2^{i-1} = (n+1) 2^{n+1} - 2^{n+1} + 1$$

Do this as follows:

$$ \sum_{i=0}^{n+1} i 2^{i-1} = \sum_{i=0}^{n} i 2^{i-1} + (n+1)2^n = n 2^n - 2^n + 1 + (n+1)2^n = n 2^{n+1} + 1 = (n+1)2^{n+1} - 2^{n+1} + 1$$

Which is what you wanted to show. Hope this helps.

$\endgroup$
  • 2
    $\begingroup$ Is this right? $(n+1)2^n+(n+1 )2^n-1 = 2(n+1)2^n-1=(n+1)2^{n+1}-1$... The OP's formula does not hold for $n=1$. $\endgroup$ – David Mitra Nov 30 '11 at 11:43
  • $\begingroup$ Darn, you're right! $\endgroup$ – Rudy the Reindeer Nov 30 '11 at 11:44
  • $\begingroup$ @DavidMitra: Let's assume it's a typo. Let's see whether I can fix this. $\endgroup$ – Rudy the Reindeer Nov 30 '11 at 11:45
  • $\begingroup$ @DavidMitra: Thanks, David. Fixed. $\endgroup$ – Rudy the Reindeer Nov 30 '11 at 11:57
  • $\begingroup$ @Sosy: Thank you, my pleasure! $\endgroup$ – Rudy the Reindeer Nov 30 '11 at 18:32
2
$\begingroup$

HINT $\ $ The RHS should be $\rm\:(n-1)\ 2^n + 1\:.\:$ As always, by telescopy, the inductive step arises from equating the first difference of the LHS and RHS. Here that yields the trivially proved identity

$$\rm (n+1)\ 2^n\ =\ n\ 2^{n+1} - (n-1)\ 2^n $$

which, combined with the trivial proof of the base case $\rm\:n=0\:,\:$ completes the proof by induction.

REMARK $\ $ Note that absolutely no ingenuity is required. The proof by telescopy is so mechanical that it can be done by a machine. Indeed, cancelling the factor of $\rm\:2^n\:,\:$ said inductive step reduces to proving the polynomial identity $\rm\ n+1\ =\ 2\:n - (n-1)\:.\:$ For much further discussion see my many posts on telescopy.

$\endgroup$
  • 1
    $\begingroup$ sounds very helpful, but hmmm what is the first difference of the LHS and RHS? at what value (k or k+1)? $\endgroup$ – Sosy Nov 30 '11 at 18:05
  • $\begingroup$ @Sosy The first difference of $\rm\:f(n)\:$ wrt $\rm\:n\:$ is $\rm\:\Delta_n f(n) := f(n+1) - f(n)\:.\:$ The displayed equation above is $\rm\: \Delta\: LHS(n) = \Delta\: RHS(n)\:.\:$ This method works to mechanically "discover" the induction step on all problems of this type. See the linked posts on telescopy for background. $\endgroup$ – Bill Dubuque Nov 30 '11 at 19:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.