I have been working on a problem and I can not figure it out. I am not looking for an answer but I am interested in figuring out what my next step should be or where I could read up on problems similar to mine.
Let $T(n)$ be defined recursively as follows: $T(18) = 14,$ and $T(n) = 2T((n/2)+5)+n$ for all $n \ge 18.$ Prove by induction on n that $T(n) = (n - 10)\log(n-10) -10$ for all $n \ge 18.$
I have solved for the base case of $n = 18$ on $T(n) = (n - 10)\log(n-10) -10 $and found that to be true.
Then I assumed $n = k$ was true and tried showing $n = k+1$ is true. I could not figure out how to do that.
Next I figured out the series of numbers that would yield a positive integer greater than or equal to $18$ if plugged in for $n.$ They are: $18, 26, 42, 74.$
I am not really sure where to go from here, what should my next step be?
Thank you
Note that the inverse of f(n) = ((n/2) + 5) is g(n) = (n-5)*2 = 2 * n - 10.
If T(n) is defined and the hypothesis holds at n, then we have T(2 * n - 10) = 2*T(n) + 2 * n - 10 = 2 * ((n-10) * log(n - 10) - 10) + 2*n - 10 = 2 * (n - 10) * log(n - 10) + 2 * n - 30
We therefore need to show that this is equal to (k - 10) * log(k - 10) - 10 evaluated at k = 2 * n - 10.
2 * n - 10 - 10 = 2 * n - 20
(2 * n - 20) * log(2 * n - 20) - 10 = 2 * (n - 10) * (1 + log(n - 10)) - 10
= 2 * (n - 10) * log(n - 10) - 10 + 2 * (n - 10) =
2 * (n - 10) * log(n - 10) + 2 * n - 30.
Therefore, for all n, if T(n) is given by the correct formula and T is defined at (2 * n - 10) then T(2 * n - 10) will also be, and vice versa.
To prove the formula for every even number, we have to show that each one is reachable from 18 by repeatedly jumping from n to 2 * n - 10 or (n/2)+5 (if n is even).