Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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
show 1 more comment

2 Answers 2

up vote 1 down vote accepted

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} $$

share|improve this answer
    
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
add comment

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) $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.