• 0 Votes - 0 Average
• 1
• 2
• 3
• 4
• 5
 Linear Recursion, more complicated
08-12-2010, 04:48 PM
Post: #1
 elim Moderator Posts: 577 Joined: Feb 2010 Reputation: 0
Linear Recursion, more complicated
$$A_{n+1}+A_n = 1, \; A_1 = 0$$
$$B_{n+3}-B_n = A_n, \quad B_j = 0,\; j = \overline{1,3}$$
$$C_{n+7}-C_n = B_n, \quad C_j = 0,\; j = \overline{1,10}$$
08-14-2010, 02:11 PM
Post: #2
 elim Moderator Posts: 577 Joined: Feb 2010 Reputation: 0
RE: Linear Recursion, more complicated
Clearly $$A_n = \frac{1}{2}(1+(-1)^n)$$
Since $$B_{n+3} = B_n + A_n$$, we have $$B_{n+4}+B_{n+3}-B_{n+1}-B_n = A_{n+1}+A_n=1$$,
The corresponding characteristic equation is $t^4+t^3-t-1 = (t-1)(t+1)(t^2+t+1)=0$
Thus $B_n = a + b(-1)^n +c\cos \frac{2n\pi}{3} +d \sin \frac{2n\pi}{3} + \frac{n}{6}$ where the last term is for the non-homogeneous right hand side, namely $1$.
From $\frac{1}{2}(1+(-1)^n)=A_n = B_{n+3}-B_n = \frac{1}{2}-2b(-1)^n$ we see that $b = -\frac{1}{4}$
From $B_1=B_2=B_3 = 0$ we get $B_n = \frac{n}{6}-\frac{1}{4}(-1)^n-\frac{5}{12}-\frac{1}{3}\cos \frac{2n\pi}{3}-\frac{\sqrt{3}}{9}\sin \frac{2n\pi}{3}$
08-14-2010, 06:01 PM
Post: #3
 elim Moderator Posts: 577 Joined: Feb 2010 Reputation: 0
RE: Linear Recursion, more complicated
Now $B_n = \frac{n}{6}-\frac{1}{4}(-1)^n + P(n)$ where $P$ has period $3$
Since $B_j = 0, \quad j = \overline{1,3}$ we see that $P(1)=-5/12, P(2)=-1/12, P(3)=-3/4$
So $-12P(n)-5 = -4((n \mod 3) -1)$ and $B_n = \frac{n}{6}-\frac{1}{4}(-1)^n -\frac{5}{12} + \frac{1}{3} ((n \mod 3) -1)$
That is $B_n = \frac{n}{6}-\frac{1}{4}(3+(-1)^n)+ \frac{1}{3} (n \mod 3)$

Periodic functions over integers can always be expressed as a function of $x = (n \mod m)$ where $m$ is the period.
 « Next Oldest | Next Newest »

Forum Jump: