Completely lost on using strong induction for this proof regarding a recursive algorithm.

Question

T(n) = 1 when n $\le$ 10

T(n) = T($\lfloor\frac{n}{5}\rfloor$) + 7 T($\lfloor\frac{n}{10}\rfloor$) + n when n $\gt$ 10

Prove by strong induction that, for all n ≥ 1, we have T (n) ≤ 10n. Hint: The only fact about ⌊ ⌋ that you will need is that when x ≥ 1, ⌊x⌋ is an integer, and 1 ≤ ⌊x⌋ ≤ x.

So here is my proof so far:

Let P(n) be T(n) < 10n We will show that P(n) is true for every integer of n $\ge$ 1 by strong induction.

Base cases (n=1, n=2 , n=3 , n=4 n=5 , n=6, n=7, n=8, n=9 and n=10) Since T(n) = 1 for all values $\le$ 10 and $\ge$ 1, we know T(n) =1 for all base cases. 1 < 10n when n $\ge$ 1, therefore P(n) is true.

Inductive hypothesis. Suppose that for some arbitrary integer k $\ge$ 10, P(j) is true for every integer 1 $\le$ j $\le$ k.

Inductive step: We want to prove that P(k+1) is true.

T(k+1) = T($\lfloor\frac{k+1}{5}\rfloor$) + 7 • T( $\lfloor\frac{k+1}{10}\rfloor$ + k + 1 by definition of T(n)

T($\lfloor\frac{k+1}{5}\rfloor$) = 1 when k $\le$ 49

T($\lfloor\frac{k+1}{10}\rfloor$) = 1 when k $\le$ 99

$\lfloor\frac{k+1}{5}\rfloor$ $\le$ $\frac{k+1}{5}$ and $\lfloor\frac{k+1}{10}\rfloor$ $\le$ $\frac{k+1}{5}$

and... now I'm kinda lost. Any tips you can give to me to push me in the right direction? I'm really new to proofs and can't figure out how to get to k+1 $\le$ 10n from here. Thanks.

Answer 1

Note that, if $n\geqslant10$, then $\left\lfloor\frac n5\right\rfloor,\left\lfloor\frac n{10}\right\rfloor<n$ and so (induction hypothesis):

• $T\left(\left\lfloor\frac n5\right\rfloor\right)\leqslant10\left\lfloor\frac n5\right\rfloor\leqslant10\times\frac n5=2n$;
• $7T\left(\left\lfloor\frac n{10}\right\rfloor\right)\leqslant7\times10\left\lfloor\frac n{10}\right\rfloor\leqslant7\times10\times\frac n{10}=7n$.

Therefore,$$T(n)=T\left(\left\lfloor\frac n5\right\rfloor\right)+7T\left(\left\lfloor\frac n{10}\right\rfloor\right)+n\leqslant2n+7n+n=10n.$$