Need someone to check my induction proof for errors

Question

I was told to solve the following recurrence relation/equation

$$T(n) = T(9n/10) + n$$

and after doing the algebra, I got the following solution

$$T(n) = 10[n - 1] $$

note: we are assuming that T(1) = $0$

(if you want to check the work i did to get the above, just check my previous post in my account)

Anyway, here is my induction proof...

BASE : $T(1) = 10[1 - 1]= 0 $

Hypothesis: Assume $T(k) = 10[k - 1]$

Induction steps: prove $T(10k/9) = 10[10k/9 - 1]$

1) $T(10k/9) = T(9n/10) + n$

I used the original recurrence equation and plugged in $10k/9$

2) $T(10k/9) = T(k) + 10k/9$

Now we plug in the hypothesis into our new equation

3) $T(10k/9) = 10[k−1] + 10k/9$

now we simplify..

4) $T(10k/9) = 10k− 10 + 10k/9$

5) $T(10k/9) = 100k/9 − 10 $

6) $T(10k/9) = 10[10k/9 - 1]$

Did I make any errors in my proof?

Any help will be appreciated

Answer 1

Let $\quad T(x)=x+T(\alpha x)\quad$ with $\vert\alpha\vert<1$. Then , using induction on $n$ you can show that: $$T(x)=x+\alpha x+\cdots+\alpha^{n}x+T\left(\alpha^{n+1}x\right), \ \forall\,n\geq 1$$ $$T(x)=x(1+\alpha+\cdots+\alpha^{n})+T(\alpha^{n+1}x) =x\frac{\ \ 1-\alpha^{n+1}}{1-\alpha}+T\left(\alpha^{n+1}x\right)$$ Suppose that $T$ is a continous function. Then taking the limit as $n$ tends to $\infty$, you get: (because $\vert\alpha\vert<1$)

$$T(x)=\frac{1}{1-\alpha}x+T(0).$$

The conclusion here is that the only continuous functions that satisfaies $T(x)=x+T(\alpha x)$ are of the form: $$T(x)=\frac{1}{1-\alpha}x+T(0)$$ Here $T(0)$ is any constant you want.

In particular, if you take $\alpha=\frac{9}{10}$ and $T(0):=-10$. You get $$T(x)=10(x-1).$$

Observe that the assumption $T(1)=0$ is equivalent to $T(0)=-10$.