Finding an exact solution to a difference equation

Question

How would I solve an equation of the form:

$u(n+1)=1/2u(n)+(1/3)^n$ when $u(0)=1$?

I got an answer of the form $u(n)= c + \sum(1/3)^j*2^{j-1}$ but believe this is incorrect?

Answer 1

Consider $u_{n+1} = \dfrac{1}{2}\cdot u_n$. This gives: $u_n = 2^{-n}$, $n\geq 0$. So the general solution would be: $u_n = a\cdot 2^{-n} + b\cdot 3^{-n}$.

$u_0 = 1 \to 1 = a + b$, and $u_1 = 0.5u_0 + 1 = \dfrac{3}{2} \to \dfrac{a}{2} + \dfrac{b}{3} = \dfrac{3}{2} \to 3a + 2b = 9 \to 3a + 2(1 - a) = 9 \to a = 7$, and $b = 1 - a = 1 - 7 = -6$. Thus:

$u_n = 7\cdot 2^{-n} - 6\cdot 3^{-n}$, $n \geq 0$

Answer 2

To know if your solution is correct, you can substitute back in the equation and check. Another approach to solve the problem would be to use Z-Transform.

Answer 3

Use a generating function: $G(z) = \sum_{k=0}^{\infty} u(k)z^k$ by multiplying LHS and RHS by $z^k$ and summing over $k$. On LHS you get $\frac{G(z) - u(0)}{z}$. Solve for $G(z)$ and then equate coefficients for $z^n$. This will be your general formula.