Unit 2: Recurrence Relations - Subjective Questions

Recurrence relation: A recurrence relation is an equation that defines each term of a sequence using one or more preceding terms.

For example,

with an initial value such as defines the entire sequence.

• Order: The order is the maximum difference between the index of the term being defined and the indices of the preceding terms. In
  
  the order is .
• Degree: After removing radicals and fractions involving sequence terms, the degree is the highest power of the highest-order sequence term. In
  
  the degree is .

Initial conditions are required to determine a unique sequence from a recurrence relation.

A recurrence relation is linear if every sequence term occurs only to the first power and sequence terms are not multiplied together. For example,

is linear. The relation

is non-linear because is squared.

A linear recurrence relation has the form

• It is homogeneous when .
• It is non-homogeneous when .

Thus,

is homogeneous, whereas

is non-homogeneous.

Let be the balance immediately after the deposit at the end of year . Assume .

Before each new deposit, the previous balance earns interest. Therefore,

Successive balances are:

• .
• .
• .

Hence, the balance immediately after the third deposit is

Let denote the minimum number of moves needed to transfer disks from one peg to another.

To move disks:

1. Move the top disks to the auxiliary peg in moves.
2. Move the largest disk to the destination peg in one move.
3. Move the disks from the auxiliary peg to the destination peg in another moves.

Therefore,

Repeated substitution gives

After substitutions,

Since and the geometric sum equals ,

Let be the number of binary strings of length with no consecutive s.

Classify valid strings according to their ending:

• A valid string ending in is obtained by appending to any valid string of length , giving strings.
• A valid string ending in must end in . Removing this leaves any valid string of length , giving strings.

Thus,

The initial values are

Therefore, is the shifted Fibonacci sequence:

where and .

Equivalently, using Binet's formula,

Consider a homogeneous linear recurrence relation of order :

Assume a trial solution . Substitution and division by produce the characteristic equation

The solution depends on its roots:

• If are distinct, then
  
• If a root has multiplicity , its contribution is
  
• Complex conjugate roots may be rewritten using sine and cosine.

Finally, the arbitrary constants are determined from the given initial conditions.

Rewrite the relation as

Its characteristic equation is

Factoring,

so the distinct roots are and . Hence,

Using ,

Using ,

Subtracting twice the first equation from the second gives , and therefore .

Thus,

The characteristic equation is

Thus, is a root of multiplicity .

For a repeated root of multiplicity , the general solution is not merely . The second independent solution must be multiplied by . Therefore,

Using ,

Using ,

so and .

Hence,

The factor appears because the characteristic root is repeated.

The characteristic equation is

Its roots are

Write these roots in polar form. Their modulus is

and their arguments are . Therefore, the real general solution is

From , . From ,

Thus, , and

Consider

where is a polynomial in the shift operator and .

The complete solution has two parts:

where:

• is the complementary solution, obtained by solving .
• is a particular solution, satisfying .

Resonance occurs when the normal trial form for the particular solution is already part of the complementary solution. For example, if and is a root of the characteristic polynomial, a trial duplicates a complementary term.

If is a root of multiplicity , the trial particular solution must be multiplied by . Thus, the modified trial is typically

The shift operator is defined by

More generally,

A linear recurrence can therefore be written in operator form as

where is a polynomial in .

Formally, a particular solution is

The symbol is called the inverse operator.

For an exponential forcing term , the shift property gives

If , this direct rule fails because of resonance. The operator must then be factored, and a suitable power of must be introduced.

Using , the recurrence becomes

or

The complementary solution is

For the particular solution,

Since is a simple root of the operator polynomial, resonance occurs. Let

Substitution into the original recurrence gives

Equating this to gives , so .

Therefore,

The associated homogeneous recurrence is

whose characteristic root is . Thus,

Since the forcing term is a polynomial of degree , assume

Substitution gives

Simplifying,

Comparing coefficients,


Therefore,

Using gives , so .

Hence,

The homogeneous equation has characteristic polynomial

Therefore,

The forcing term is the degree- polynomial . Since is a characteristic root of multiplicity , the ordinary polynomial trial resonates with the complementary solution. Use

The left side is the second backward difference. Substitution gives

Equating coefficients with gives

Thus,

Hence,

Using gives , and using gives

Therefore,

For a sequence , its ordinary generating function is the formal power series

It encodes the entire sequence as coefficients of powers of .

Important generating functions include:

• For ,
  
• Differentiating the geometric series and multiplying by gives
  
• Replacing by in the geometric series gives
  

Analytically, these identities hold within their radii of convergence. In recurrence problems, they may also be treated as identities of formal power series.

Let

For the first shifted sum, set :

For the second shifted sum, set :

Related identities needed when the index is not shifted inside the sequence are

and

These formulas allow a recurrence relation to be converted into an algebraic equation for .

Let

Multiply the recurrence by and sum for :

Using the initial values,

Hence,

Let

Since

partial fractions give

Using , the coefficient of is

Define

Multiply the recurrence by and sum for :

Therefore,

Solving for ,

Partial fractions yield

Expanding each term as a geometric series,

Thus, the coefficient of is

The generalized binomial-series identity is

Taking gives

Therefore, if

then coefficient comparison gives

Equivalently,

The first few terms are

These are triangular numbers shifted so that the sequence begins at .

Characteristic-root method

• Best suited to homogeneous linear recurrence relations with constant coefficients.
• It converts the recurrence into a polynomial equation.
• Initial conditions determine the constants in the complementary solution.

Inverse-operator method

• Particularly useful for non-homogeneous linear recurrence relations with constant coefficients.
• It separates the solution into complementary and particular parts.
• It handles exponential, polynomial, and trigonometric forcing terms efficiently, but resonance must be treated carefully.

Generating-function method

• Converts the recurrence and its initial conditions into an algebraic equation for a power series.
• It works well for combinatorial recurrences, convolution-type relations, and coefficient extraction.
• Partial fractions or known power-series identities are usually required to obtain a closed form.

All three methods can solve many constant-coefficient recurrences. The characteristic-root method is usually shortest for homogeneous relations, the inverse-operator method directly targets non-homogeneous forcing terms, and generating functions provide a systematic approach that incorporates initial conditions from the beginning.