# Solving Linear, Homogeneous Recurrences (and Differential Equations)

Page 1 of 1

## 4 Replies - 33720 Views - Last Post: 23 June 2011 - 06:40 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=236549&amp;s=10f1a1318a63f2085b94858f1d50eb98&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11315
• Posts: 42,632
• Joined: 27-December 08

# Solving Linear, Homogeneous Recurrences (and Differential Equations)

Posted 21 June 2011 - 07:04 PM

POPULAR

This tutorial will introduce how to solve nth order linear, homogeneous recurrences. Since certain forms of differential equations can be solved with the same process, they will be included as well. However, the primary focus will remain on recurrences.

To start, let's discuss what constitutes a mathematical recurrence. It is a mathematical formula that relies on previous cases in the calculations for the current case. Recurrences must have at least one base case where the formula is equivalent to an actual value rather than a previous case. Programatically, this allows for computing the nth term in a recurrence in O(1) time, as the general form equations don't rely on previous cases.

The first step when solving any linear, homogeneous recurrence (or differential equation) is to solve for 0. So for example, given the Fibonacci recurrence: F(n) = F(n-1) + F(n-2), solve so: F(n) - F(n-1) - F(n-2) = 0. An equivalent differential equation might look like: y" - y' - y = 0.

The next step is to set up the characteristic equation, which is simply a polynomial function. To obtain this, take the difference between the highest parameter and the lowest parameter. In the Fibonacci recurrence, the difference is two (n - (n-2)), so the characteristic equation is a quadratic. With differential equations, the difference in the order of derivatives is used to determine the power of the characteristic equation. So y" is a 2nd order derivative, and y is a 0 order derivative, still leaving a quadratic.

Thus the characteristic equation for both the Fibonacci recurrence and the differential equation is: r2 - r - 1 = 0. The next step is to find the roots of the characteristic equation, which are called eigenvalues. Different general forms are used based on whether the eigenvalues are real and distinct, real and repeated, or complex. These equations are similar for linear recurrences and differential equations, with the major difference being that the recurrence solutions have the eigenvalues as the bases, and the differential equation solutions have e as the bases. The formulas are as follows:

Real and Distinct Roots:
• Linear Recurrences: f(n) = A(r1)n + B(r2)n
• Differential Equations: f(t) = Ae(r1)t + Be(r2)t

Real and Repeated Roots:
• Linear Recurrences: f(n) = Arn + Bnrn
• Differential Equations: f(t) = Aert + Btert

Complex Roots (where r = a +- bi):
• Linear Recurrences: f(n) = Dancos(bn) + Gansin(bn)
• Differential Equations: f(t) = Deatcos(bt) + Geatsin(bt)

The equations for the complex roots come from Euler's formula: eit = cos(t) + isin(t). Since r1 = a + bi, and r2 = a - bi, the solution can be written as: f(n) = e(a+bi)n + e(a-bi)n. Further simplification with trig identities will result in the above equations. It is assumed that you have already covered this in a precalculus or calculus course. While the first two equations can be used, it may be easier in many cases to rely on this third equation.

After selecting the appropriate general form equation from above, the final step is to set up a system of equations around the base cases. Given the Fibonacci recurrence, the base cases are: F(0) = 0 and F(1) = 1. Knowing that the Fibonacci eigenvalues are (1 +- sqrt(5))/2, the system of equations can be set up:
0 = A + B
1 = A(1 + sqrt(5))/2 + B(1-sqrt(5))/2

Solving this leaves A = sqrt(5)/5 and B = sqrt(5)/5, and the final recurrence as:
F(n) = sqrt(5)/5 * [(1+sqrt(5))/2]n - sqrt(5)/5 * [(1-sqrt(5))/2]n

Let's look at one final example: f(n) = 2f(n-1) - 2f(n-2), with the base cases f(0) = 1, and f(1) = 1.

The first step is to solve for 0:
f(n) - 2f(n-1) + 2f(n-2) = 0

From here, the characteristic equation (a quadratic) becomes:
r2 - 2r + 2 = 0

Since this cannot be factored, the quadratic equation will have to be used to solve for the eigenvalues:
r = [2 +- sqrt(4 - 4(1)(2))]/2
r = 1 +- i

Since the roots are complex, the equation f(n) = D(1)ncos(n) + G(1)nsin(-n). Or more simply: f(n) = Dcos(n) - Gsin(n).

Setting up the system of equations with the eigenvalues leaves:
f(0) = 1 = Dcos(0) + Gsin(0)
f(1) = 1 = Dcos(1) + Gsin(1)

Since sin(0) = 0 and cos(0) = 1, the f(0) equation cancels out leaving D = 1. From there, solving f(1) equation: 1 = cos(1) + Gsin(1) leaves G = (1-cos(1))/sin(1).

Thus the recurrence solution is: f(n) = cos(n) + (1-cos(1))/sin(1) * sin(n).

Conclusion
While solving recurrences may seem like a lot of work on the front end, it can save a lot of computational time when compared to implementing the recursive or iterative solutions. This math on the front end will allow either human or computer to find the nth term (especially for large values of n) in O(1) time vs. O(n) and greater for the more naive solutions.

Is This A Good Question/Topic? 5

## Replies To: Solving Linear, Homogeneous Recurrences (and Differential Equations)

Reputation: 0
• Posts: 15
• Joined: 15-March 10

## Re: Solving Linear, Homogeneous Recurrences (and Differential Equations)

Posted 23 June 2011 - 05:33 AM

May i know why it has to be y"-y'-y=0 and not y"+y'-y = 0?

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11315
• Posts: 42,632
• Joined: 27-December 08

## Re: Solving Linear, Homogeneous Recurrences (and Differential Equations)

Posted 23 June 2011 - 05:54 AM

Because y"-y'-y =0 produces the same characteristic equation as the Fibonacci recurrence.
F(n) - F(n-1) - F(n-2) = 0
y" - y' - y = 0

Both have a difference in order of 2, so that leaves us with a quadratic. Since y" and F(n) both have a coefficient of 1, the r2 is positive. F(n-1), F(n-2), y' and y all have coefficients of -1, so those are the corresponding coefficients in the characteristic equation, which is: r2 - r - 1 = 0.

Reputation: 0
• Posts: 15
• Joined: 15-March 10

## Re: Solving Linear, Homogeneous Recurrences (and Differential Equations)

Posted 23 June 2011 - 06:36 AM

If i am not wrong, F(n) is the second derivative and not f(n-2). Am i correct?
Can you please provide me any online source to learn the basics of differential equations? Sorry I lost touch in mathematics after working as a software professional. I need to get it back. Thanks in advance..

Please note that the function should return double and not integer in the snippet you written for fibonacci series with O(1) notation.

This post has been edited by ahamedirshad123: 23 June 2011 - 06:39 AM

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11315
• Posts: 42,632
• Joined: 27-December 08

## Re: Solving Linear, Homogeneous Recurrences (and Differential Equations)

Posted 23 June 2011 - 06:40 AM

F(n), the Fibonacci function, is not a derivative. It is discrete, not continuous. The reason I included linear, homogeneous, differential equations with this tutorial is b/c the method to solve them is the same as with the recurrences. But linear, homogeneous recurrences != linear, homogeneous differential equations.

One resource I like for Differential Equations is Paul's Notes.

Quote

Please note that the function should return double and not integer in the snippet you written for fibonacci series with O(1) notation.

Technically, Fibonacci numbers aren't continuous, so it should return an int, not a double.