Proof Using Strong Induction

**jgm51672** · July 25th 2009, 07:57 PM

Can anyone help me get started with the proof attached. I have to use strong induction.

**CaptainBlack** · July 25th 2009, 10:24 PM

Originally Posted by jgm51672

Can anyone help me get started with the proof attached. I have to use strong induction.

Check the base case (for simplicity make the base case all $n$ up to $6$ ), I will assume you have done so.

Now suppose for some $k>6$ that: for all $0 < r \le k$ that $T(r)<4n$

Now consider:

$T(k+1)=T(\lfloor (k+1)/3 \rfloor)+T(\lfloor (k+1)/5 \rfloor)+T(\lfloor (k+1)/7 \rfloor)+(k+1)$

which by assumption:

............. $<\frac{4(k+1)}{3}+\frac{4(k+1)}{5}+\frac{4(k+1)}{7 }+(k+1)$

Now you should be able to finish this yourself.

CB

**jgm51672** · July 27th 2009, 06:30 AM

kindly.

Thread: Proof Using Strong Induction

LinkBack

Thread Tools

Display

Proof Using Strong Induction

Thank you

Similar Math Help Forum Discussions

proof by strong induction

Strong Induction proof

Proof by strong induction?

Strong Induction proof

Strong induction proof

Search Tags