Proof of Induction

**BabyMilo** · April 21st 2010, 01:28 AM

It is given that $sn=2*2+3*2^2+4*2^2+........ +(n+1)*2^n$

a) By first considering the values of $\frac{S1}{1}$ , $\frac{S2}{2}$ , $\frac{S3}{3}$ , $\frac{S4}{4}$ and making a conjecture for a formula for $\frac{Sn}{n}$ , make a conjecture for a formula for Sn.

b) Use induction to prove that your conjecture is correct.

For a) i did $S1=4, S2=6, S3=8$

so the conjecture for $Sn=2n+2$

b) $S1=4$ , $S1=2*1+2=4$
so n=1 is true.

$Sk=2k+2$
$Sk+1=2(k+1)+2 = 2k+4$

what do i do next? or how to i prove $Sk+1=2k+4$

thanks.

**HallsofIvy** · April 21st 2010, 02:56 AM

Originally Posted by BabyMilo

It is given that $sn=2*2+3*2^2+4*2^2+........ +(n+1)*2^n$

a) By first considering the values of $\frac{S1}{1}$ , $\frac{S2}{2}$ , $\frac{S3}{3}$ , $\frac{S4}{4}$ and making a conjecture for a formula for $\frac{Sn}{n}$ , make a conjecture for a formula for Sn.

b) Use induction to prove that your conjecture is correct.

For a) i did $S1=4, S2=6, S3=8$

No, S2= 2(2)+ 3(4)= 4+ 12= 16, not 6 and S3= 2(2)+ 3(4)+ 4(8)= 4+ 12+ 32= 48, not 8.

Why not do what you were told to do- look at Sn/n first?

S1/1= 4, S2/2= 8, S3/3= 48/3= 16, ...

so the conjecture for $Sn=2n+2$

b) $S1=4$ , $S1=2*1+2=4$
so n=1 is true.

$Sk=2k+2$
$Sk+1=2(k+1)+2 = 2k+4$

what do i do next? or how to i prove $Sk+1=2k+4$

thanks.

**BabyMilo** · April 21st 2010, 03:22 AM

Originally Posted by HallsofIvy

No, S2= 2(2)+ 3(4)= 4+ 12= 16, not 6 and S3= 2(2)+ 3(4)+ 4(8)= 4+ 12+ 32= 48, not 8.

Why not do what you were told to do- look at Sn/n first?

S1/1= 4, S2/2= 8, S3/3= 48/3= 16, ...

so i have $\frac{Sn}{n} = 2^{n+1}$

$\rightarrow Sn=2^{n+1}*n$

**BabyMilo** · April 21st 2010, 04:27 AM

Originally Posted by BabyMilo

so i have $\frac{Sn}{n} = 2^{n+1}$

$\rightarrow Sn=2^{n+1}*n$

now im stuck on

$2^{k+2}+2(2^{k+1}*k) = 2^{k+2}*(k+1)$

**Archie Meade** · April 21st 2010, 05:06 AM

Originally Posted by BabyMilo

now im stuck on

$2^{k+2}+2(2^{k+1}*k) = 2^{k+2}*(k+1)$

Hi BabyMilo,

P(k)

$S_k=k2^{k+1}$

then we try to express P(k+1) in terms of P(k) to find out if there is a cause

P(k+1)

$S_{k+1}=(k+1)2^{k+2}$

Let's see if this is what we get when we add the (k+1)th term to $S_k$

$S_k+T_{k+1}=k2^{k+1}+(k+2)2^{k+1}$

since the (k+1)th term is $(k+1+1)2^{k+1}$

$S_k+T_{k+1}=2^{k+1}(k+k+2)=2(k+1)2^{k+1}=(k+1)2^{k +2}$

As $S_k$ being valid will cause $S_{k+1}$ to be valid,

there is a cause and effect relationship, so you only need test the first one.

**BabyMilo** · April 21st 2010, 06:00 AM

Originally Posted by Archie Meade

Hi BabyMilo,

P(k)

$S_k=k2^{k+1}$

then we try to express P(k+1) in terms of P(k) to find out if there is a cause

P(k+1)

$S_{k+1}=(k+1)2^{k+2}$

Let's see if this is what we get when we add the (k+1)th term to $S_k$

$S_k+T_{k+1}=k2^{k+1}+(k+2)2^{k+1}$

since the (k+1)th term is $(k+1)2^{k+1+1}$

$S_k+T_{k+1}=2^{k+1}(k+k+2)=2(k+1)2^{k+1}=(k+1)2^{k +2}$

As $S_k$ being valid will cause $S_{k+1}$ to be valid,

there is a cause and effect relationship, so you only need test the first one.

Can you show me how you got from

to $S_k+T_{k+1}=2^{k+1}(k+k+2)$

**Archie Meade** · April 21st 2010, 10:02 AM

Originally Posted by BabyMilo

Can you show me how you got from

to $S_k+T_{k+1}=2^{k+1}(k+k+2)$

Yes,

if we take $2^{k+1}$ as the common factor of both terms

$2^{k+1}[k]+2^{k+1}(k+2)=2^{k+1}\left([k]+(k+2)\right)$

Thread: Proof of Induction

LinkBack

Thread Tools

Display

Proof of Induction

Similar Math Help Forum Discussions

Proof using induction

Induction Proof

Mathemtical Induction Proof (Stuck on induction)

Proof by induction

Proof with algebra, and proof by induction (problems)

Search Tags