# Strong induction inequality proof using floor

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

• 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. – Fox Apr 9 '19 at 19:42
• I added some information in the answer. So I hope it becomes more obvious now. – guest Apr 10 '19 at 3:25
• Thanks a ton! I bow down to your superior understanding of induction. – Fox Apr 10 '19 at 12:58