My professor showed this inequality to class today and I've been having a tough time trying to solve it. I know that I have to use strong induction but don't know how to progress farther than the 2 base cases(n=1, n=2).

Recurrence relation: $$F(i) = \begin{cases} 1, & i \leq 2\\ 3 F(\lfloor\frac{i}{3}\rfloor) + 5i, & i > 2 \end{cases}$$

To prove: $ F(n) \leq 4n \cdot log_{2}(n) +1 $


For the induction step assume that F(n) ≤ 4n·log2(n)+1 for n∈ℕ.
Then, we get for k∈{0,1,2}:
F(3n+k) = 3F(⌊3n+k/3⌋)+5(3n+k) = 3F(n)+5(3n+k) ≤ 3(4n·log2(n)+1)+5(3n+k) = 12n·log2(n)+3+5(3n+k) ≤ 12n·log2(n)+6(3n+k) < 4(3n+k)·log2(n)+4(3n+k)·log2(3) = 4(3n+k)·log2(3n) < 4(3n+k)·log2(3n+k)+1
And this is everything we had to prove.

To the second equal sign:
We have k∈{0,1,2} such that k/3 < 1. So we get
n ≤ n+k/3 < n+1
And (because n is a natural number) this inequality leads to
⌊n+k/3⌋ = n
And this results in
3n+k/3⌋ = ⌊3n/3+k/3⌋ = ⌊n+k/3⌋ = n

  • $\begingroup$ After the second equal sign, you convert F(floor((3n+k)/3)) to just F(n). How exactly does this work? You'll have to forgive me if I'm missing something incredibly obvious, we haven't actually formally learned about floor function yet. $\endgroup$ – Fox Apr 9 '19 at 19:42
  • $\begingroup$ I added some information in the answer. So I hope it becomes more obvious now. $\endgroup$ – guest Apr 10 '19 at 3:25
  • $\begingroup$ Thanks a ton! I bow down to your superior understanding of induction. $\endgroup$ – Fox Apr 10 '19 at 12:58

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.