Learning Recurrence Relations: Challenges & Solutions

• SYoungblood
In summary, recurrence relations can be challenging to understand, especially when it comes to determining the starting point and finding a formula for the general solution. However, with practice and understanding of the recursion, it is possible to find solutions for negative values of n as well.
SYoungblood

Homework Statement

: [/B]
I am just learning recurrence relations, and they are proving challenging.

Homework Equations

-- [/B]Let's have xn = 3xn-1 + 6xn-2.
I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4

The Attempt at a Solution

Is there a difference between having a staring point of x0and x1? That is the sticking point.

As far as the solution is concerned, if I wanted to go to the 5th term, I can do the x1=3 and x2 = 4 scenario -- x1 = 1, x2 = 4, x3 = x3=30, x4 = 114, and x5= 522.

The scenario with x0 is challenging to me. How can you have a recurrence relation where the n-1 term leaves you a negative number? How do you know where to start? Is it understood that, in the equation that is above, I would start with 3(x0(or 3 * 1) + 6(x1(6 * 3), with a sum of 21?

Also, how would you turn this into a formula? How do you determine the degree? For this last question, I just need a point in the right direction, I'm not asking for someone to do the questions for me.

SYoungblood said:

Homework Statement

: [/B]
I am just learning recurrence relations, and they are proving challenging.

Homework Equations

-- [/B]Let's have xn = 3xn-1 + 6xn-2.
I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4

The Attempt at a Solution

Is there a difference between having a staring point of x0and x1? That is the sticking point.

As far as the solution is concerned, if I wanted to go to the 5th term, I can do the x1=3 and x2 = 4 scenario -- x1 = 1, x2 = 4, x3 = x3=30, x4 = 114, and x5= 522.

The scenario with x0 is challenging to me. How can you have a recurrence relation where the n-1 term leaves you a negative number? How do you know where to start? Is it understood that, in the equation that is above, I would start with 3(x0(or 3 * 1) + 6(x1(6 * 3), with a sum of 21?

Also, how would you turn this into a formula? How do you determine the degree? For this last question, I just need a point in the right direction, I'm not asking for someone to do the questions for me.

The usual way of writing these things is as ##x_n = 3 x_{n-1} + 6x_{n-2} \; \text{for} \; \; n \geq 2##, with ##x_0=1, x_1 = 3##. In other words, the recursion does not apply when ##n = 0, 1##.

If you wanted a formula you could try ##x_n = r^n## for some ##r##. Then, the recursion would give ##r^n = 3 r^{n-1}+ 6 r^{n-2}##, or ##r^2 = 3 r + 6##. This is a quadratic, and so has two roots, usually---in this case it does have two real roots. So, the general solution would be of the form
$$x_n = A r_1^n + B r_2^n, \; n \geq 2$$
where ##r_1, r_2## are the two roots. We can find values of ##A, B## either by (i) requiring that this expression hold as well for ##n = 0,1##; or (ii) computing ##x_2, x_3## from the recursion as well as from the above formula, giviing two equations for ##A,B##.

Thank you, this is something to speak about w/ the prof, it is still not sinking in.

In some cases, you can solve for negative n using the same recurrence relation. Given $x_{n}$ and $x_{n-1}$, you can solve for $x_{n-2}$:
$$x_n = 3x_{n-1} + 6x_{n-2} \\ x_{n-2} = (x_n - 3x_{n-1}) / 6 \\ x_1 = 3 \\ x_0 = 0 \\ x_{-1} = 1/2 \\ x_{-2} = -1/4 \\ x_{-3} = 5/24 \\ x_{-4} = -7/48 \\ x_{-5} = 31/288 \\ ...$$

Last edited:

1. What is a recurrence relation?

A recurrence relation is a mathematical equation that describes a sequence of values, where each value is defined in terms of previous values in the sequence. It is often used in computer science and mathematics to model and analyze complex systems.

2. What are the challenges of learning recurrence relations?

Learning recurrence relations can be challenging because it requires a strong understanding of mathematical concepts such as sequences, series, and functions. It also involves the use of advanced techniques such as mathematical induction and solving recurrence relations using closed-form solutions.

3. What are some common solutions to understanding recurrence relations?

One solution is to practice solving various types of recurrence relations using different techniques. Another approach is to break down the problem into simpler, well-known patterns and then apply them to the recurrence relation. Seeking help from a tutor or attending a workshop on recurrence relations can also be helpful.

4. How can recurrence relations be applied in real-life situations?

Recurrence relations can be used to model and analyze various real-life situations, such as population growth, financial investments, and computer algorithms. They can also be used to predict future outcomes and make informed decisions based on past data.

5. Are there any resources available for learning recurrence relations?

Yes, there are many online tutorials, videos, and textbooks available that cover the basics of recurrence relations and provide practice problems. Additionally, many universities offer courses on discrete mathematics or algorithms that cover recurrence relations in depth.

• Precalculus Mathematics Homework Help
Replies
3
Views
3K
• Precalculus Mathematics Homework Help
Replies
6
Views
9K
• MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
2K
• Differential Equations
Replies
1
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Programming and Computer Science
Replies
1
Views
1K
• MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
872
• Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
• Precalculus Mathematics Homework Help
Replies
22
Views
3K