Unit2 - Subjective Questions

Definition:
A recurrence relation for the sequence is an equation that expresses in terms of one or more of the previous terms of the sequence, namely , for all integers with , where is a nonnegative integer.

Order of a Recurrence Relation:
The difference between the highest and lowest subscripts of the terms appearing in the equation is called the order of the recurrence relation. For a relation expressed as , the order is .

Example:
The Fibonacci sequence is defined by the linear recurrence relation:

Modelling:
Let denote the number of moves required to solve the Tower of Hanoi puzzle with disks. To move disks from peg A to peg C:

1. Move the top disks from A to B ( moves).
2. Move the largest disk from A to C ($1$ move).
3. Move the disks from B to C ( moves).

Thus, the recurrence relation is:

Solution:
Calculating the first few terms:

Pattern: .

Verification:
Substitute into the relation: . (True).

Step 1: Characteristic Equation
The associated characteristic equation is:

Step 2: Find Roots

Step 3: Apply Initial Conditions
For :
For :

Substitute into the second equation:
.
Then, .

Final Solution:

Linear Recurrence Relation with Constant Coefficients:
A relation of the form:

1. Homogeneous:
If the Right Hand Side (RHS), , is exactly zero for all , the relation is called homogeneous.

• Example:

2. Non-Homogeneous:
If $f(n)
eq 0n$, or a constant), the relation is called non-homogeneous.

• Example:
• Example:

Step 1: Characteristic Equation

Step 2: Find Roots

Step 3: General Solution
For repeated roots of multiplicity 2, the solution is of the form:

Step 4: Constants

• :
• :

Final Solution:

If the characteristic equation has complex roots and , we can express these roots in polar form:

• Magnitude
• Argument

The standard solution involves complex numbers.

Using De Moivre's theorem (), the solution can be rewritten in real form as:

Where and are arbitrary real constants determined by initial conditions.

Rewriting in operator form where is the shift operator ( implies ).
Usually, we convert indices to positive shifts or use characteristic polynomial form directly in the denominator.
Operator form: . Let's solve for directly from roots.

1. Homogeneous Solution ():
Char. Eq: .
Roots: $2, 3$.

2. Particular Solution ():
Using Inverse Operator Method:

3. Total Solution:

Let the recurrence relation be , where is a polynomial in of degree . The particular solution is given by:

Procedure:

1. Recall the relation between the Shift operator and the Forward Difference operator : .
2. Substitute into the denominator: .
3. Expand as a power series in up to the term .
   • Terms higher than are ignored because the difference of a polynomial of degree is zero.
4. Apply the expanded operators to .
   • , etc.

This yields the particular polynomial solution.

Operator Form:
is not quite right standard form. Let's look at characteristic form:
(Shifted RHS) or simply treat standard form: acting on equals RHS.
Let's assume the relation corresponds to where .

Substitute :

Here, represents the Inverse Difference operator (Antidifference or Summation).
(Usually indefinite sum implies in factorial polynomial notation).
Using standard polynomial summation: .
.

Note: If the characteristic roots include 1 (as here, root is 1 with multiplicity 2), standard polynomial ansatz must be multiplied by . Inverse operator handles this naturally via .

Definition:
The generating function for the sequence is the infinite power series:

Example ():
Sequence:

This is a geometric series with first term and common ratio .
The sum converges for .

Expansion:
We know the standard expansions:

Substitute into A(x):

Coefficient :

The Sequence:

Sequence:

Let .
Multiply the recurrence by and sum from to :

Rewrite in terms of G(x):

Equation:

Partial Fractions:

Solving for A and B:

Set :
Set :

Simplify the Series:
The term inside the bracket is a geometric series with ratio :

Expression:
The generating function is:

Binomial Expansion:
Using the extended binomial theorem: .
Here and .

Finding :
We need , so .
The coefficient is .

Concept:
Modeling involves translating a real-world problem involving sequential steps or growth into a mathematical equation linking current states to previous states.

Compound Interest Model:
Let be the amount in a savings account after years.
Let be the principal amount.
Let be the annual interest rate (e.g., for 5%).

Relation:
The amount after years equals the amount after years plus the interest earned on that amount.

Solution:
This is a first-order linear homogeneous relation.


General Solution:

Statement:
If is the generating function for the sequence , then is the generating function for the sequence shifted to the right by positions, with leading zeros.

Proof:
Let .
Multiply by :

We can rewrite this summation letting (so ):

This corresponds to the sequence: (where the first non-zero term is at index ).

1. Define G(x):
.

2. Multiply and Sum:
The relation is valid for .

Sum from to :

3. Substitution:

4. Isolate G(x):

5. Partial Fractions:

• :
• :

6. Solution:

Rule for Failure Case:
If we have and , the standard substitution fails.

This occurs when is a root of the characteristic polynomial. Let the multiplicity of the root be .

The rule is:

Alternatively, using the derivative method similar to differential equations (often easier to remember as multiplying by ):
If , differentiate with respect to and multiply the numerator by (conceptually).
More formally, for a simple root ():
(Adjustments needed for discrete context, typically form is ).

Let .
Recurrence: for .

Multiply by and sum from to :

Substitute initial conditions :

Step 1: Characteristic Equation

Step 2: Factorization
This is a standard binomial expansion for :

Step 3: Roots
The root is with multiplicity 3.

Step 4: General Solution
For a root repeated times, the solution is .
Here :

This represents a quadratic in .

Convolution Property:
If and , then where .

Problem:
.
Here, both and correspond to the sequence (since ).
So, and for all .

Calculate coefficient :

Result:
The sequence is (i.e., ).