How to find a non-recursive formula for a recursively defined sequence

Question

Given:

$\mu(0)=0$

$\mu(i)= 2\mu(i-1) + 2^{i-1} \ \ \ \ \ \ \forall i \in N $

I would like to know if there is any way of obtaining the non recursive formula for $\mu (i)$:

$\mu(i) = i2^{i-1}$

That doesn't rely on figuring it out by looking the patterns and then proving it by induction.

Answer 1

Let $f(z)=\sum_{n=0}^\infty \mu(n)z^n$ be the ordinary generating function. The recurrence relation implies that $$\sum_{n=1}^\infty \mu(n) z^n = 2 \sum_{n=1}^\infty\mu(n-1)z^n + \sum_{n=1}^\infty 2^{n-1} z^n,$$ equivalently, $$f(z) - \mu(0)z^0 = 2 z f(z) + z \cdot\frac{1}{1-2z}.$$ Solving for $f(z)$ yields $$f(z)=\frac{z}{(1-2z)^2},$$ whose partial fraction decomposition $$f(z)=\frac{-1/2}{1-2z}+\frac{1/2}{(1-2z)^2}=\frac{-1}{2}\sum_{n=0}^\infty (2z)^n+\frac{1}{2}\sum_{n=0}^\infty \binom{n+1}{1}(2z)^n$$ immediately implies that $$\mu(n)=\frac{-1}{2}2^n+\frac{1}{2}\binom{n+1}{1}2^n=-2^{n-1}+(n+1)2^{n-1}=n2^{n-1}.$$

Answer 2

Define $$a_n=\frac {\mu_n}{2^{n-1}}$$

Then, $$a_0=0\quad \&\quad a_n=\frac {2\mu_{n-1}+2^{n-1}}{2^{n-1}}=\frac {\mu_{n-1}}{2^{n-2}}+1=a_{n-1}+1$$

which implies that $a_n=n$, and we are done.