How to solve this recurrence relation ?

**denniszeng2008@gmail.com** · April 19th 2009, 01:27 AM

3P(n) = 1-P(n-1).
P(n) = ???
Thanks in advance.

**CaptainBlack** · April 19th 2009, 01:47 AM

Originally Posted by denniszeng2008@gmail.com

3P(n) = 1-P(n-1).
P(n) = ???
Thanks in advance.

Could you please post the complete question.

CB

**denniszeng2008@gmail.com** · April 19th 2009, 04:23 AM

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) = ?

**aidan** · April 19th 2009, 06:38 AM

Originally Posted by denniszeng2008@gmail.com

3P(n) = 1-P(n-1).
P(n) = ???
Thanks in advance.

if
3P(n) = 1-P(n-1)

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

**denniszeng2008@gmail.com** · April 19th 2009, 06:58 AM

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

**Soroban** · April 19th 2009, 07:48 AM

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] <br /> 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]$

**denniszeng2008@gmail.com** · April 19th 2009, 04:31 PM

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

Thread: How to solve this recurrence relation ?

LinkBack

Thread Tools

Display

How to solve this recurrence relation ?

Complement

But

Similar Math Help Forum Discussions

big o recurrence relation

Solve the recurrence relation...

Solve the recurrence relation

Help with recurrence relation

Recurrence relation

Search Tags