Integer linear recurrence sequences of order 2 for dummies

Fibonacci!

F_0 = 0\\F_1 = 1\\F_n=F_{n-1}+F_{n-2}

It goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

So, what do you think? Kind of remarkable, with those irrational numbers, trigonometric functions, complex roots, and chaos, right? What? You don’t see them? Look more closely.

Take ratios of consecutive Fibonacci numbers and they approach \phi=(1+\sqrt{5})/2 = 1.61803..., the “Golden Ratio”. Weird, right? It’s all integers, and yet they point to an irrational number:

n Fn Fn/Fn-1
0 0
1 1
2 1 1
3 2 2
4 3 1.5
5 5 1.666666667
6 8 1.6
7 13 1.625
8 21 1.615384615
9 34 1.619047619
10 55 1.617647059
11 89 1.618181818
12 144 1.617977528
13 233 1.618055556
14 377 1.618025751
15 610 1.618037135

But the Fibonacci sequence is just one instance of a more general integer linear recurrence sequence of order 2, defined by:

L_0 = 0\\L_1 = 1\\L_n=pL_{n-1}+qL_{n-2}

where p, q are integer constants. p=1,q=1 gives the Fibonacci sequence. (One can get even more general by choosing other starting values;  p=1,q=1,L_0=2,L_1=1 gives the Lucas sequence, for instance. But for our purposes let’s stick with L_0=0, L_1=1.)

Keeping p=1 but using q=10 we get a sequence that increases much faster, not surprisingly. It looks like the ratio of consecutive terms converges to about 3.7, but the convergence is much slower:

n Ln Ln/Ln-1
0 0
1 1
2 1 1
3 11 11
4 21 1.909090909
5 131 6.238095238
6 341 2.603053435
7 1651 4.841642229
8 5061 3.0654149
9 21571 4.262201146
10 72181 3.346205554
11 287891 3.988459567
12 1009701 3.507233641
13 3888611 3.851250024
14 13985621 3.596559543
15 52871731 3.780434991

If someone asks you, “what’s the next number in this sequence? 0, 1, 2, 3, 4, 5…” you can say, “that’s easy, it’s an integer linear recurrence sequence of order 2 with p=2,q=-1,L_0=0,L_1=1:”

n Ln Ln/Ln-1
0 0
1 1
2 2 2
3 3 1.5
4 4 1.333333333
5 5 1.25
6 6 1.2
7 7 1.166666667
8 8 1.142857143
9 9 1.125
10 10 1.111111111
11 11 1.1
12 12 1.090909091
13 13 1.083333333
14 14 1.076923077
15 15 1.071428571

And there of course the ratios of consecutive terms converge to 1.0, but slowly.

It might take you a little longer to come to grips with 0, 1, 1, –1, –3, –1, 5, 7, –3… though. But that’s just p=1,q=-2:

n Ln Ln/Ln-1
0 0
1 1
2 1 1
3 -1 -1
4 -3 3
5 -1 0.3333333333
6 5 -5
7 7 1.4
8 -3 -0.4285714286
9 -17 5.666666667
10 -11 0.6470588235
11 23 -2.090909091
12 45 1.956521739
13 -1 -0.02222222222
14 -91 91
15 -89 0.978021978

Whoah, chaotic! Doesn’t look like that one’s consecutive term ratio is converging to anything. Or diverging. It’s just all over the place.

One more: p=2,q=-2:

n Ln Ln/Ln-1
0 0
1 1
2 2 2
3 2 1
4 0 0
5 -4
6 -8 2
7 -8 1
8 0 0
9 16
10 32 2
11 32 1
12 0 0
13 -64
14 -128 2
15 -128 1

Huh. Not converging, but not chaotic. So what’s going on?

Well, let’s go back to the Fibonacci sequence. It seems to be connected with \phi. And in fact, a closed formula is

F_n = \left[\phi^n/\sqrt{5}\right]

where [x] denotes the nearest integer to x. Or another formula:

F_n = \frac{\phi^n-\left(-\phi^{-n}\right)}{\sqrt{5}}

Wait, what? You’re taking ratios of differences of powers of irrational numbers and irrational numbers and getting integers? Well, yes. Because powers of \phi and -1/\phi contain terms with even powers of \sqrt{5}, which are positive integers and cancel in the difference, and odd powers of -\sqrt{5}, which are negative integers times \sqrt{5}; those don’t cancel in the difference, and then the factor of \sqrt{5} cancels in the ratio, so you’re left with integers. Still, seems kind of weird, this intimate relationship between \phi and the Fibonacci sequence.

But consider this quadratic equation:

x^2 = x + 1

whose solutions are \phi and \psi=(1-\sqrt{5})/2=-1/\phi. Then \phi and \psi also are solutions of

x^n = x^{n-1}+x^{n-2}

(which is just the previous equation multiplied by x^{n-2}). If we define U(n)=a\phi^n+b\psi^n, where a and b are constants, then

U(n)=a\phi^n+b\psi^n=a(\phi^{n-1}+\phi^{n-2})+b(\psi^{n-1}+\psi^{n-2})\\=a\phi^{n-1}+b\psi^{n-1}+a\phi^{n-2}+b\psi^{n-2}\\=U(n-1)+U(n-2)

so U(n) satisfies the Fibonacci recurrence relation, and if we solve the simultaneous equations

U(0)=F_0=0\\U(1)=F_1=1

we get a = 1/\sqrt{5} = -b, and with those values, U(n) = F_n. Ta daa.

Well, we can generalize this. Consider the sequence

S(0)=0\\S(1)=1\\S(n)=pS(n-1)+qS(n-2)

where p and q are integers; this is an integer linear recurrence sequence. To get a closed formula for S(n) start with the equation

x^2=px+q

whose solutions are \lambda_{1,2}=(p\pm\sqrt{p^2+4q})/2. If p^2+4q\ne 0, then setting S(n) to a linear combination of the \lambdas gives you the general solution — I won’t prove that, but it’s true.You can find a proof elsewhere, e.g. here. Imposing S(0)=0, S(1)=1 you get the particular solution

S(n)=\frac{\lambda_1^n-\lambda_2^n}{\sqrt{p^2+4q}}.

What if p^2+4q=0? Then \lambda_1=\lambda_2=\lambda=p/2 and the general solution is U(n)=a\lambda^n+bn\lambda^n. (Once again, follow the above link or do some Googling if you want the proof.) Imposing S(0)=0, S(1)=1 you get

S(n)=n\left(\frac{p}{2}\right)^{n-1}.

So what’s the behavior as n increases? If p^2+4q>0 and |\lambda_1|>|\lambda_2| then as n gets large, S(n) approaches \lambda_1^n/\sqrt{p^2+4q} and the ratio S(n)/S(n-1) approaches \lambda_1. Similarly ifp^2+4q>0 and |\lambda_2|>|\lambda_1|, the ratio approaches \lambda_2. Clearly the larger the difference in magnitude of the \lambdas the faster this convergence happens.

If p^2+4q=0, the ratio of consecutive terms approaches p/2.

And what if p^2+4q<0? Now it’s a whole new ball game; the \lambdas are complex, with |\lambda_1|=|\lambda_2|. Taking the case p>0, we have

\lambda_{1,2}=\frac{p}{2}\pm i\frac{\sqrt{-\left(p^2+4q\right)}}{2}\\=\sqrt{-q}e^{\pm i\theta}

where \theta=\arcsin{\frac{\sqrt{-(p^2/4+q)}}{\sqrt{-q}}}=\arcsin{\sqrt{1+\frac{p^2}{4q}}}. Now

S(n)=\frac{\lambda_1^n-\lambda_2^n}{\sqrt{p^2+4q}}\\=\frac{2\left(\sqrt{-q}\right)^n}{\sqrt{-\left(p^2+4q\right)}}\Im e^{\pm in\theta}

(\Im denotes imaginary part)

S(n)=\frac{\left(\sqrt{-q}\right)^{n-1}}{\sqrt{1+p^2/4q}}\sin{\left(n\arcsin{\sqrt{1+p^2/4q}}\right)}

When p<0 you get something similar, but multiplied by (-1)^{n-1}.

(So, uh, wait, we’re saying that right hand side is always an integer? Yes. You want proof? Heh.)

And that means the behavior as n increases is… well. It’s complicated, isn’t it? That \sin{(n\theta)} throws a monkey wrench into the whole business.

So let’s go back to our examples from above. If p=q=1 then we have the Fibonacci series. \lambda_{1,2}=\phi,\psi and |\phi| is about two and a half times larger than |\psi|, so the ratio of consecutive values converges quickly to \phi.

If p=1,q=10 then \lambda_{1,2}=3.70156...,-2.70156...; the ratio converges to 3.70156 but more slowly.

The case p=2,q=-1 gives p^2+4q=0, so the ratio approaches 2/2=1. Specifically it’s n/(n-1), so the convergence is pretty slow.

And for p=1,q=-2, p^2+4q<0 and

S(n)=\frac{1.414214^{n-1}}{.935414}\sin{1.209429 n}

and the ratios of consecutive terms don’t behave smoothly.

The p=2,q=-2 case also has p^2+4q<0, but in this case the angle is \theta=\arcsin{\sqrt{2}/2}=\pi/4, so the value of \sin{n\theta} repeats after four steps and the sequence behaves regularly, with the ratios of consecutive terms cycling through 2, 1, 0, (undefined).

So you see? You thought when we started all this was just multiplying and adding integers. We ended up with irrationals and powers of complex numbers and trigonometric functions and chaos and all kinds of stuff. Amazing.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s