2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.