Practice Math Induction Prove 1

harpazo

Pure Mathematics
1 + (2x2) + (3x2^2) +...+ (n x (2^(n-1)) = 1+(n-1)(2^n)
 

MarkFL

La Villa Strangiato
Math Helper
The induction hypothesis \(P_n\) here is:

[MATH]\sum_{k=1}^n\left(k2^{k-1}\right)=1+(n-1)2^n[/MATH]
So, we first check the validity of the base case \(P_1\):

[MATH]\sum_{k=1}^1\left(k2^{k-1}\right)=1+(1-1)2^1[/MATH]
[MATH]1=1\quad\checkmark[/MATH]
The base case is true, so it seem natural that our inductive step will be to add [MATH](n+1)2^n[/MATH] to both sides of \(P_n\):

[MATH]\sum_{k=1}^n\left(k2^{k-1}\right)+(n+1)2^n=1+(n-1)2^n+(n+1)2^n[/MATH]
[MATH]\sum_{k=1}^{n+1}\left(k2^{k-1}\right)=1+(n-1+n+1)2^n[/MATH]
[MATH]\sum_{k=1}^{n+1}\left(k2^{k-1}\right)=1+((n+1)-1)2^{n+1}[/MATH]
We have derived \(P_{n+1}\) for \(P_n\), thereby completing the proof by induction.
 
Last edited:

harpazo

Pure Mathematics
The induction hypothesis \(\P_n) here is:

[MATH]\sum_{k=1}^n\left(k2^{k-1}\right)=1+(n-1)2^n[/MATH]
So, we first check the validity of the base case \(P_1\):

[MATH]\sum_{k=1}^1\left(k2^{k-1}\right)=1+(1-1)2^1[/MATH]
[MATH]1=1\quad\checkmark[/MATH]
The base case is true, so it seem natural that our inductive step will be to add [MATH](n+1)2^n[/MATH] to both sides of \(P_n\):

[MATH]\sum_{k=1}^n\left(k2^{k-1}\right)+(n+1)2^n=1+(n-1)2^n+(n+1)2^n[/MATH]
[MATH]\sum_{k=1}^{n+1}\left(k2^{k-1}\right)=1+(n-1+n+1)2^n[/MATH]
[MATH]\sum_{k=1}^{n+1}\left(k2^{k-1}\right)=1+((n+1)-1)2^{n+1}[/MATH]
We have derived \(P_{n+1}\) for \(P_n\), thereby completing the proof by induction.

I know you enjoy proofs.
 
Top