Finding the least upper bound for a sequence

36 Views Asked by At

Define $f(1) = 10$ and $f(n) = f(\lfloor n/2\rfloor) + f(\lfloor n/3\rfloor) + 17n$.

Find the smallest value $k$ so that $f(n) \leq kn$ for all $n$.


I plugged in $f(1)$ into the function, which lead me to $2 \cdot f(0) + 17 = 10,$ so $f(0) = -7/2$.

Then I calculated $f(2) = f(1) + f(0) + 34 = 10 -7/2 + 34 =40.5$

Also $f(3) = f(1) + f(1) + 17(3) = 71$ and $f(4) = f(2) + f(1) + 17(4) = 118.5$

I don't see a clear pattern. I think it oscillates back and forth, but I can't get anything.

Any help is appreciated.