# Math Help - Proof Using Strong Induction

1. ## Proof Using Strong Induction

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

2. 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

kindly.