Question

Solve the following linear recurrences. a. \(x_{k+2}=3 x_{k}+2 x_{k+1},\) where \(x_{0}=1\) and \(x_{1}=1\) b. \(x_{k+2}=2 x_{k}-x_{k+1},\) where \(x_{0}=1\) and \(x_{1}=2\). c. \(x_{k+2}=2 x_{k}+x_{k+1},\) where \(x_{0}=0\) and \(x_{1}=1\). d. \(x_{k+2}=6 x_{k}-x_{k+1},\) where \(x_{0}=1\) and \(x_{1}=1\).

Short answer

a. \(x_k = \frac{1}{2}(3^k) + \frac{1}{2}(-1)^k\); b. \(x_k = 1\); c. \(x_k = \frac{1}{3}(2^k) - \frac{1}{3}(-1)^k\); d. \(x_k = \frac{2}{5}(2^k) + \frac{3}{5}(-3)^k\)."}

Step-by-step solution

Introduction to Recurrence Relation

A recurrence relation is an equation that recursively defines a sequence. We can express the next term in a sequence as a function of the preceding terms.

General Solution Approach

For linear recurrence relations with constant coefficients, such as the ones given, the characteristic equation can be solved to find the solution. The general form is: if the recurrence is \(a_k x_{k+2} + b_k x_{k+1} + c_k x_k = 0\), then the characteristic equation is \(r^2 + (b_k / a_k)r + (c_k / a_k) = 0\).

Problem a – Characteristic Equation

The recurrence relation is \(x_{k+2} = 3x_k + 2x_{k+1}\). The characteristic equation is \(r^2 - 2r - 3 = 0\).

Problem a – Solving Characteristic Equation

Solve \(r^2 - 2r - 3 = 0\) using the quadratic formula: \[r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]where \(a=1, b=-2, c=-3\). The roots are \(r_1 = 3\) and \(r_2 = -1\).

Problem a – General Solution of the Recurrence

The general solution is \(x_k = A(3^k) + B(-1)^k\).

Problem a – Apply Initial Conditions

Substitute \(x_0 = 1\) and \(x_1 = 1\) to solve for \(A\) and \(B\). This gives two equations: 1. \(A + B = 1\)2. \(3A - B = 1\)Solving these, \(A = \frac{1}{2}\), \(B = \frac{1}{2}\).

Problem a – Particular Solution

The particular solution is \(x_k = \frac{1}{2}(3^k) + \frac{1}{2}(-1)^k\).

Problem b – Characteristic Equation

The recurrence is \(x_{k+2} = 2x_k - x_{k+1}\). The characteristic equation is \(r^2 + r - 2 = 0\).

Problem b – Solving Characteristic Equation

Solve \(r^2 + r - 2 = 0\): \[r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]where \(a=1, b=1, c=-2\). The roots are \(r_1 = 1\) and \(r_2 = -2\).

Problem b – General Solution of the Recurrence

The general solution is \(x_k = A1^k + B(-2)^k = A + B(-2)^k\).

Problem b – Apply Initial Conditions

Use \(x_0 = 1\) and \(x_1 = 2\) to solve for \(A\) and \(B\). This gives:\(A + B = 1\) and \(A - 2B = 2\).Solving, \(A = 1\), \(B = 0\).

Problem b – Particular Solution

The particular solution is \(x_k = 1\).

Problem c – Characteristic Equation

For the recurrence \(x_{k+2} = 2x_k + x_{k+1}\), the characteristic equation is \(r^2 - r - 2 = 0\).

Problem c – Solving Characteristic Equation

Solve \(r^2 - r - 2 = 0\): \[r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]where \(a=1, b=-1, c=-2\). The roots are \(r_1 = 2\), \(r_2 = -1\).

Problem c – General Solution of the Recurrence

The general solution is \(x_k = A(2^k) + B(-1)^k\).

Problem c – Apply Initial Conditions

Using \(x_0 = 0\) and \(x_1 = 1\), solve for \(A\) and \(B\):\(A + B = 0\) and \(2A - B = 1\).Solving, \(A = \frac{1}{3}\), \(B = -\frac{1}{3}\).

Problem c – Particular Solution

The particular solution is \(x_k = \frac{1}{3}(2^k) - \frac{1}{3}(-1)^k\).

Problem d – Characteristic Equation

The recurrence is \(x_{k+2} = 6x_k - x_{k+1}\). The characteristic equation is \(r^2 + r - 6 = 0\).

Problem d – Solving Characteristic Equation

Solve \(r^2 + r - 6 = 0\): \[r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]where \(a=1, b=1, c=-6\). The roots are \(r_1 = 2\), \(r_2 = -3\).

Problem d – General Solution of the Recurrence

The general solution is \(x_k = A(2^k) + B(-3)^k\).

Problem d – Apply Initial Conditions

Using \(x_0 = 1\) and \(x_1 = 1\), solve for \(A\) and \(B\):\(A + B = 1\) and \(2A - 3B = 1\).Solving, \(A = \frac{2}{5}\), \(B = \frac{3}{5}\).

Problem d – Particular Solution

The particular solution is \(x_k = \frac{2}{5}(2^k) + \frac{3}{5}(-3)^k\).

Key concepts

Characteristic Equation

When dealing with linear recurrence relations, the characteristic equation is a powerful tool. It helps in extracting solutions that describe the behavior of the sequence over time. To construct the characteristic equation from a given recurrence relation, translate the sequence's linear equation into a polynomial equation in terms of the root variable \(r\).
For example, if you have a recurrence relation given by \(x_{k+2} = ax_{k+1} + bx_k\), its characteristic equation becomes \(r^2 - ar - b = 0\). This transformation allows us to find the roots \(r_1\) and \(r_2\), which then lead to the general form solution.
The roots of this equation are crucial as they indicate whether the sequence is growing, shrinking, or oscillating. With these roots, the general solution of the recurrence relation typically has the form \(x_k = A(r_1)^k + B(r_2)^k\), where \(A\) and \(B\) are constants determined by initial conditions.

Initial Conditions

Initial conditions are the values at the start of a sequence, such as \(x_0\) and \(x_1\). They are essential in defining the specific sequence we're looking for, out of infinitely many sequences that the general form of the recurrence might suggest.
These conditions allow us to solve for the constants \(A\) and \(B\) in the general solution form. By substituting the initial values into equations derived from the solution formula, we get a system of linear equations that can be solved to find \(A\) and \(B\).
Without the initial conditions, the solution remains too general. They tailor the general form to fit exactly the sequence designated by the recurrence relation. Correctly solving this part ensures that our sequence satisfies the entire recurrence relation from beginning to end.

Particular Solution

A particular solution of a linear recurrence relation is a specific solution that fits the initial conditions. It is derived after finding the general solution and applying the initial conditions.
This solution satisfies both the recurrence relation and the starting points dictated by the initial conditions. Usually, it appears in the form \(x_k = A(r_1)^k + B(r_2)^k\) after substituting the calculated values of \(A\) and \(B\).
For different sets of initial conditions, a different particular solution will be derived. Even though the general solution gives us a wide net of possible sequences, the particular solution matches exactly the sequence in question.

• Verify that the initial values computed match the given initial conditions.
• Ensure that the particular sequence satisfies the original recurrence relation for several terms.

With the particular solution, you move from a general understanding to the precise numerical sequence needed.