Iteration Substitution, and $T(n)$ where $n = 0$

Question

Iteration Substitution / Plug and Chug method

Hi, I'm currently working on recurrence relation. And I'm having trouble on iteration problems, such as:

$$T(n) = 1 + \frac 12\, T\left(\frac n2\right), \quad T(0) = 2$$

And if, for instance, I have already formulated a formula with respect to i, such as: $$ \dfrac {n^2}i = 0 $$ I just don't know what to do, as when I try to separate $n$ and $i$, I would just get $n^2 = 0$ or the other way around. How would I go about these kind of problems?

Edit:

The only way I know right now is by substituting $0$ with a variable $x$. That way, I could get some formula. But I still don't know what to do afterwards. $$ x = 0;\\ \frac{n^2}{i}\ = x \\ \frac{n^2}{x}\ = i $$

Answer 1

You can search for constant solutions $c$.

Substituting in the equation gives $c=1+\frac 12c\iff c=2$

Let shift the solution to get rid of the annoying constant $1$ : $$U(n)=T(n)-2$$

We get: $\require{cancel}\quad U(n)=T(n)-2=\left(1+\frac 12 T(\frac n2)\right)-2=\left(\cancel{1}+\frac 12(U(\frac n2)+\cancel{2})\right)-\cancel{2}$

We get the simplified relation: $$U(n)=\frac 12 U(n/2)$$

Let set $n=2^p$ and $V(p)=U(2^p)$

$V(p)=U(2^p)=\frac 12U(2^p/2)=\frac 12U(2^{p-1})=\frac 12V(p-1)$

This induction relation is easy to solve:

$V(p)=\frac 12V(p-1)=\frac 14V(p-2)=\frac 18V(p-3)=\cdots=\frac 1{2^p}V(0)$

We can now express $T(n)$ while going back the chain of substitutions :

$V(0)=U(2^0)=U(1)=T(1)-2$

$V(p)=U(2^p)=U(n)=T(n)-2=\dfrac{V(0)}{2^p}=\dfrac{T(1)-2}{n}$

Final result $$T(n)=\frac{T(1)-2}{n}+2$$

---

Solving initial condition $T(0)=2$ requires $T(1)=2$ else this quantity would be infinite.

In this case $T(n)=2,\ \forall n\in\mathbb N$.

Answer 2

The only solution that is bounded at the origin is the constant function $T(n) = 2$. This is because we can iterate the relation to obtain $$T(n) = 1 + \frac{1}{2} + \frac{1}{4} + \ldots + \frac{1}{2^k} + \frac{1}{2^{k+1}} T\Big(\frac{n}{2^{k+1}}\Big)$$ which tends to $2$ as $k \to \infty$, regardless of $n$.