# How to solve this recurrence relation ?

• Apr 19th 2009, 01:27 AM
denniszeng2008@gmail.com
How to solve this recurrence relation ?
3P(n) = 1-P(n-1).
P(n) = ???
• Apr 19th 2009, 01:47 AM
CaptainBlack
Quote:

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

Could you please post the complete question.

CB
• Apr 19th 2009, 04:23 AM
denniszeng2008@gmail.com
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) = ?
• Apr 19th 2009, 06:38 AM
aidan
Quote:

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
• Apr 19th 2009, 06:58 AM
denniszeng2008@gmail.com
But
But i want to figure out a p(n) = n 's function but not a recurrence sequence.
• Apr 19th 2009, 07:48 AM
Soroban
Hello, denniszeng!

Quote:

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

$\displaystyle \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]: .$\displaystyle 3X^{n+1} -3X^n \:=\:-X^n + X^{n-1} \quad\Rightarrow\quad X^{n+1} - 3X^n - X^{n-1} \:=\:0$

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

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

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

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

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

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

Substitute into [3]:

. . $\displaystyle \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: .$\displaystyle A \:=\:\frac{1}{4},\quad B \:=\:\tfrac{3}{4}(1 - 4a)$

Therefore: .$\displaystyle 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]$

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

• Apr 19th 2009, 04:31 PM
denniszeng2008@gmail.com
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) = $\displaystyle 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