# Thread: How to solve this recurrence relation ?

1. ## How to solve this recurrence relation ?

3P(n) = 1-P(n-1).
P(n) = ???

2. Originally Posted by denniszeng2008@gmail.com
3P(n) = 1-P(n-1).
P(n) = ???
Could you please post the complete question.

CB

3. ## Complement

it is only a recursive problem.
3P(n) = 1 - P(n-1)
3P(n-1) = 1 - P(n - 2)
...
How to figure out P(n) = ?

4. Originally Posted by denniszeng2008@gmail.com
3P(n) = 1-P(n-1).
P(n) = ???
if
3P(n) = 1-P(n-1)

then
P(n) = (1-P(n-1))/3

5. ## But

But i want to figure out a p(n) = n 's function but not a recurrence sequence.

6. Hello, denniszeng!

$3\!\cdot\!P(n) \:=\: 1-P(n-1)\qquad\text{Find }P(n)$
Let $P(n) \:=\:X^n$

$\begin{array}{cccccc}\text{Then we have:} &3X^n &=& 1-X^{n-1} & [1] \\ \text{The next term:} & 3X^{n+1} &=& 1 - X^n & [2] \end{array}$

Subtract [2] - [1]: . $3X^{n+1} -3X^n \:=\:-X^n + X^{n-1} \quad\Rightarrow\quad X^{n+1} - 3X^n - X^{n-1} \:=\:0$

Divide by $X^{n-1}\!:\;\;3X^2 -2X - 1 \:=\:0 \quad\Rightarrow\quad (X-1)(3X+1) \:=\:0$

. . Hence: . $X \:=\:1,\:\text{-}\tfrac{1}{3}$

Then $P(n)$ is of the form: . $P(n) \;=\;A(1^n) + B\left(\text{-}\tfrac{1}{3}\right)^n$

. . That is: . $P(n) \:=\:A + B\frac{(\text{-}1)^n}{3^n}$ .[3]

Suppose the first term is $a\!:\;\;P(1) \:=\:a$

Then the second term is: $P(2) \:=\:\tfrac{1}{3}(1-a)$

Substitute into [3]:

. . $\begin{array}{ccccccc}P(1) \:=\:a\!:& & A - \frac{B}{3}&=& a \\ \\[-4mm]
P(2) \:=\:\frac{1}{3}(1-a)\!: && A + \frac{B}{9} &=& \frac{1}{3}(1-a) \end{array}$

Solve the system: . $A \:=\:\frac{1}{4},\quad B \:=\:\tfrac{3}{4}(1 - 4a)$

Therefore: . $P(n) \;=\;\frac{1}{4} + \frac{3}{4}(1-4a)\frac{(\text{-}1)^n}{3^n} \;=\;\frac{1}{4}\left[1 + (\text{-}1)^n\,\frac{3(1-4a)}{3^n}\right]$

. . . . . . . . $P(n) \;=\;\frac{1}{4}\left[1 + (\text{-}1)^n\frac{1-4a}{3^{n-1}}\right]$

7. But Why P(n) can have that form relate to 1 and 1/3 ?
since it is only a special example we pick that p(n) = $x^n$
Thanks very much!

I don't want to only know the solution, can you teach me how to analyze this ?
When i encounter such a problem, what should i do to figure out the right solution ?
Thanks