# Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$ if $s_1 = 0, s_2 = 0, s_3 = 1$

I have attempted to use $p_n = c2^{n-2} - d$ [where $h_n = A(3)^n$, but to no avail] - i ended up with $c=-1$ and $d=-\frac{1}{2}$, which is incorrect.

Any help is appreciated! Thanks.

Edit: solution I require is $\frac{1}{2} (3^{n-1}+1-2^n)$

Edit2: Solutions to the homogeneous equation would be of the form $h_n = A(\alpha)^n + B(\beta)^n$, and $p_n$ will exist such that $s_n = h_n + p_n$

-
Here is the technique. – Mhenni Benghorbal May 18 '13 at 8:25
Here is another way you can go. – Mhenni Benghorbal May 18 '13 at 8:26
@Mhenni My problem is I do not know the correct "guess" for $h_n$. If I know that, I am equipped to do the rest (the links you showed me aren't helpful in that regard). Uros, yes, I'm sure. – Clinton May 18 '13 at 8:34
Use induction on n! That's the easiest way out there! – Somabha Mukherjee May 18 '13 at 8:38
haha somabha, i was given the answers at the back of the book, how do i use induction otherwise? :P – Clinton May 18 '13 at 8:40

## 2 Answers

Let $t_n := \frac{s_n}{3^n}$. Hence, $t_n = t_{n-1} + 3^{-n}\left(2^{n-2} - 1\right)$. Also, $t_1 = 0$. Hence, $$t_n = \sum_{k = 2}^n \frac{1}{4}\left(\frac{2}{3}\right)^n - 3^{-n}$$ This is a geometric series and easily evaluated to arrive at $$t_n = \frac{1}{2}\cdot 3^{-n} \cdot \left(1 - 2^{n}\right) + \frac{1}{6} \implies s_n = \frac{1 + 3^{n-1}- 2^{n}}{2}$$

-
thank you! but i require to do it the substitution guessing method :\ – Clinton May 18 '13 at 8:39
The amount of notation you introduced without any sort of definitions makes it impossible to follow what you attempted. For one, you define $p_n$ then don't even bother to use it. So I can't really tell where you went wrong or what you even tried. I did perform a substitution though, so it seems like you could refactor my solution into something you want. – Jon Claus May 18 '13 at 8:45
added what they meant - maybe it's a unique method to our lecturer :P – Clinton May 18 '13 at 8:52
never mind, got it, thanks! – Clinton May 18 '13 at 8:59

A general technique is taught by Wilf's "generatingfunctionology". Define $S(z) = \sum_{n \ge 0} s_n z^n$ and write ($s_0$ you get from the recurrence "backwards", mostly for not having to mess around with indices): $$s_{n + 1} = 3 s_n + 2^{n - 1} - 1 \qquad s_0 = \frac{1}{6}$$ Multiply the recurrence by $z^n$, add over $n \ge 0$ to get: \begin{align*} \frac{S(z) - s_0}{z} &= 3 S(z) + \frac{1}{2} \sum_{n \ge 0} 2^n z^n - \sum_{n \ge 0} z^n \\ &= 3 S(z) + \frac{1}{2} \frac{1}{1 - 2 z} - \frac{1}{1 - z} \end{align*} Solving for $S(z)$ and expanding in partial fractions: $$S(z) = \frac{1}{6} \frac{1}{1 - 3 z} - \frac{1}{2} \frac{1}{1 - 2 z} + \frac{1}{2} \frac{1}{1 - z}$$ Everything in sight is geometric series: $$s_n = \frac{1}{6} \cdot 3^n - \frac{1}{2} \cdot 2^n + \frac{1}{2} = \frac{1}{2} \left( 3^{n - 1} - 2^{n - 1} + 1 \right)$$

-