Recurrence Relations

Table of Contents


Introduction to Recurrence Relations:

Recurrence relations provide a mathematical framework for defining sequences and functions based on previous terms. They are widely used in various fields, including computer science, combinatorics, and number theory.


Definition of Recurrence Relations:

A recurrence relation expresses the terms of a sequence as a function of the preceding terms. In general, for a sequence $ a_n $, a recurrence relation may define $ a_n $ in terms of $ a_{n-1}, a_{n-2}, \ldots $.

Example:

$ a_n = 2a_{n-1} + 1 $ with $ a_0 = 3 $

This recurrence defines each term of the sequence using the previous term and a constant.


Types of Recurrence Relations:

  1. Linear Recurrence Relations:
    • A recurrence relation is linear if each term is a linear combination of the preceding terms.
    • Example: $ a_n = 3a_{n-1} – 2a_{n-2} $
  2. Non-linear Recurrence Relations:
    • The recurrence is non-linear if it involves terms raised to a power or multiplied together.
    • Example: $ a_n = a_{n-1}^2 + a_{n-2} $

Homogeneous Recurrence Relations:

A recurrence relation is homogeneous if it does not contain a term that is independent of $ a_n $.

Example: $ a_n = 5a_{n-1} – 6a_{n-2} $

This is homogeneous because every term on the right-hand side involves $ a_n $ or $ a_{n-1} $.


Non-homogeneous Recurrence Relations:

In contrast, a recurrence relation is non-homogeneous if it contains terms that are independent of $ a_n $.

Example: $ a_n = 2a_{n-1} + 4 $

The constant 4 makes this a non-homogeneous recurrence relation.


First-Order Recurrence Relations:

A first-order recurrence relation is one in which the current term is defined using only the immediately preceding term.

Example: $ a_n = 3a_{n-1} + 2 $

This relation involves only the previous term, making it first-order.


Second-Order Recurrence Relations:

A second-order recurrence relation involves the current term and the two preceding terms.

Example: $ a_n = 2a_{n-1} – 3a_{n-2} $

This relation is second-order because it uses both $ a_{n-1} $ and $ a_{n-2} $.


Solving Recurrence Relations by Iteration:

One method to solve recurrence relations is by iteration, where each term is calculated one by one using the recurrence relation.

Example: For $ a_n = 2a_{n-1} + 3 $ with $ a_0 = 1 $:

  • $ a_1 = 2(1) + 3 = 5 $
  • $ a_2 = 2(5) + 3 = 13 $
  • $ a_3 = 2(13) + 3 = 29 $

Characteristic Equation Method:

For linear recurrence relations with constant coefficients, the characteristic equation method is often used to find the general solution.

Example: For $ a_n = 2a_{n-1} + a_{n-2} $, the characteristic equation is: $ r^2 – 2r – 1 = 0 $

Solve for $ r $ to find the roots, which help in determining the general solution.


Particular Solution for Non-homogeneous Recurrence Relations:

For non-homogeneous recurrence relations, the general solution is the sum of the solution to the homogeneous part and a particular solution to the non-homogeneous part.

Example: For $ a_n = 2a_{n-1} + 4 $, a particular solution could be a constant value, say $ a_n = c $, and we solve for $ c $ by substituting into the equation.


Recurrence Relations with Constant Coefficients:

A recurrence relation has constant coefficients if the coefficients multiplying the terms are constants.

Example: $ a_n = 3a_{n-1} + 4a_{n-2} $

In this case, the coefficients 3 and 4 are constant.


Divide and Conquer Recurrence Relations:

In algorithm analysis, divide and conquer strategies often lead to recurrence relations. These relations describe the time complexity of recursive algorithms.

Example: For merge sort, the recurrence relation for time complexity is: $ T(n) = 2T\left( \frac{n}{2} \right) + n $


Master Theorem for Recurrence Relations:

The Master Theorem provides a shortcut for solving divide and conquer recurrence relations.

For recurrences of the form: $ T(n) = aT\left( \frac{n}{b} \right) + f(n) $

The Master Theorem offers different cases based on the comparison of $ n^{\log_b a} $ and $ f(n) $.


Generating Functions and Recurrence Relations:

A generating function can be used to solve recurrence relations by transforming the recurrence into an algebraic equation.

Example: For the Fibonacci sequence, $ a_n = a_{n-1} + a_{n-2} $, the generating function can simplify the solution process.


Recurrence Relations in Algorithm Analysis:

Recurrence relations are commonly used to analyze recursive algorithms, particularly to determine their time complexity.

Example: The time complexity of binary search is described by the recurrence: $ T(n) = T\left( \frac{n}{2} \right) + 1 $


Applications of Recurrence Relations in Computer Science:

  • Analyzing algorithms like merge sort, quick sort, binary search, etc.
  • Used in dynamic programming to describe optimal substructure properties.

Solving Recurrence Relations Using Matrix Methods:

Recurrence relations can also be solved using matrix methods. This is especially useful for higher-order relations.

Example: The Fibonacci sequence can be expressed as a matrix multiplication problem and solved efficiently.


Recurrence Relations in Discrete Mathematics:

Recurrence relations often arise in combinatorics, where they describe sequences like the number of ways to arrange objects or solve counting problems.

Example: The recurrence relation for the number of ways to climb a staircase with 1 or 2 steps is: $ a_n = a_{n-1} + a_{n-2} $


Linear Recurrence Relations with Variable Coefficients:

In some cases, the coefficients of the recurrence relation are not constants but depend on $ n $.

Example: $ a_n = (n+1)a_{n-1} + n $


Recurrence Relations in Combinatorics:

Combinatorial problems, like counting the number of ways to arrange objects, often involve recurrence relations.

Example: The number of ways to place non-attacking rooks on a chessboard follows a recurrence relation.


Fibonacci Sequence as a Recurrence Relation:

One of the most famous examples of a recurrence relation is the Fibonacci sequence, defined by: $ F_n = F_{n-1} + F_{n-2} $ with $ F_0 = 0 $ and $ F_1 = 1 $


Lucas Numbers and Recurrence Relations:

Lucas numbers are another sequence defined by a recurrence relation similar to the Fibonacci sequence: $ L_n = L_{n-1} + L_{n-2} $ with $ L_0 = 2 $ and $ L_1 = 1 $


Recurrence Relations in Number Theory:

Recurrence relations appear in number theory, such as the recurrence relation for Pell’s equation or partition functions.

Example: The partition function $ p(n) $, which counts the number of ways to express $ n $ as a sum of integers, satisfies a recurrence relation.


Applications of Recurrence Relations in Real-Life Problems:

Recurrence relations are used in various real-world scenarios such as:

  • Population growth modeling.
  • Financial modeling for compound interest.
  • Solving problems related to network flow and communication.

Challenges in Solving Recurrence Relations:

  • Non-linear recurrence relations are often much harder to solve.
  • Finding particular solutions for non-homogeneous recurrence relations can be challenging without additional tools like generating functions or matrix methods.

Conclusion:

Recurrence relations play a crucial role in various branches of mathematics, computer science, and engineering. Whether modeling algorithms, analyzing sequences, or solving real-world problems, understanding the behavior of recurrence relations is essential.


Question And Answer Library

Example 1: Simple Recurrence Relation

Problem:
Define the recurrence relation $a_n = 2a_{n-1} + 1$ with $a_0 = 3$. Calculate $a_3$.

Answer:

Step 1: Given Data:
$a_0 = 3$

Step 2: Solution:
$a_1 = 2a_0 + 1 = 2(3) + 1 = 7$
$a_2 = 2a_1 + 1 = 2(7) + 1 = 15$
$a_3 = 2a_2 + 1 = 2(15) + 1 = 31$

Step 3: Final Answer:
$a_3 = 31$.


Example 2: Linear Homogeneous Recurrence

Problem:
Given the recurrence $a_n = 4a_{n-1} – 4a_{n-2}$ with initial conditions $a_0 = 1$, $a_1 = 2$, find $a_4$.

Answer:

Step 1: Given Data:
$a_0 = 1$, $a_1 = 2$

Step 2: Solution:
$a_2 = 4a_1 – 4a_0 = 4(2) – 4(1) = 4$
$a_3 = 4a_2 – 4a_1 = 4(4) – 4(2) = 8$
$a_4 = 4a_3 – 4a_2 = 4(8) – 4(4) = 16$

Step 3: Final Answer:
$a_4 = 16$.


Example 3: Non-Homogeneous Recurrence

Problem:
Solve the recurrence $a_n = 3a_{n-1} + 2$ with $a_0 = 1$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 3a_0 + 2 = 3(1) + 2 = 5$
$a_2 = 3a_1 + 2 = 3(5) + 2 = 17$
$a_3 = 3a_2 + 2 = 3(17) + 2 = 53$

Step 3: Final Answer:
$a_3 = 53$.


Example 4: Second-Order Linear Homogeneous

Problem:
Solve $a_n = 5a_{n-1} – 6a_{n-2}$ with initial conditions $a_0 = 2$, $a_1 = 8$.

Answer:

Step 1: Given Data:
$a_0 = 2$, $a_1 = 8$

Step 2: Solution:
$a_2 = 5a_1 – 6a_0 = 5(8) – 6(2) = 34$
$a_3 = 5a_2 – 6a_1 = 5(34) – 6(8) = 142$

Step 3: Final Answer:
$a_3 = 142$.


Example 5: Recurrence with Variable Coefficients

Problem:
Calculate $a_n = (n+1)a_{n-1}$ with $a_0 = 1$. Find $a_3$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 2a_0 = 2(1) = 2$
$a_2 = 3a_1 = 3(2) = 6$
$a_3 = 4a_2 = 4(6) = 24$

Step 3: Final Answer:
$a_3 = 24$.


Example 6: Fibonacci Recurrence

Problem:
Define the Fibonacci sequence $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$, $F_1 = 1$. Find $F_5$.

Answer:

Step 1: Given Data:
$F_0 = 0$, $F_1 = 1$

Step 2: Solution:
$F_2 = F_1 + F_0 = 1 + 0 = 1$
$F_3 = F_2 + F_1 = 1 + 1 = 2$
$F_4 = F_3 + F_2 = 2 + 1 = 3$
$F_5 = F_4 + F_3 = 3 + 2 = 5$

Step 3: Final Answer:
$F_5 = 5$.


Example 7: Lucas Numbers

Problem:
Define the Lucas sequence $L_n = L_{n-1} + L_{n-2}$ with $L_0 = 2$, $L_1 = 1$. Find $L_4$.

Answer:

Step 1: Given Data:
$L_0 = 2$, $L_1 = 1$

Step 2: Solution:
$L_2 = L_1 + L_0 = 1 + 2 = 3$
$L_3 = L_2 + L_1 = 3 + 1 = 4$
$L_4 = L_3 + L_2 = 4 + 3 = 7$

Step 3: Final Answer:
$L_4 = 7$.


Example 8: Recurrence Relation for Factorials

Problem:
Define $a_n = n \cdot a_{n-1}$ with $a_0 = 1$. Find $a_5$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 1 \cdot a_0 = 1 \cdot 1 = 1$
$a_2 = 2 \cdot a_1 = 2 \cdot 1 = 2$
$a_3 = 3 \cdot a_2 = 3 \cdot 2 = 6$
$a_4 = 4 \cdot a_3 = 4 \cdot 6 = 24$
$a_5 = 5 \cdot a_4 = 5 \cdot 24 = 120$

Step 3: Final Answer:
$a_5 = 120$.


Example 9: Non-linear Recurrence

Problem:
Define the recurrence $a_n = a_{n-1}^2 + 1$ with $a_0 = 2$. Find $a_3$.

Answer:

Step 1: Given Data:
$a_0 = 2$

Step 2: Solution:
$a_1 = a_0^2 + 1 = 2^2 + 1 = 5$
$a_2 = a_1^2 + 1 = 5^2 + 1 = 26$
$a_3 = a_2^2 + 1 = 26^2 + 1 = 677$

Step 3: Final Answer:
$a_3 = 677$.


Example 10: Recurrence Relation with a Constant

Problem:
Define the recurrence $a_n = a_{n-1} + 3$ with $a_0 = 1$. Find $a_4$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = a_0 + 3 = 1 + 3 = 4$
$a_2 = a_1 + 3 = 4 + 3 = 7$
$a_3 = a_2 + 3 = 7 + 3 = 10$
$a_4 = a_3 + 3 = 10 + 3 = 13$

Step 3: Final Answer:
$a_4 = 13$.


Example 11: Recurrence Relation for Exponential Growth

Problem:
Define the recurrence relation $a_n = 2a_{n-1}$ with $a_0 = 1$. Find $a_5$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 2a_0 = 2(1) = 2$
$a_2 = 2a_1 = 2(2) = 4$
$a_3 = 2a_2 = 2(4) = 8$
$a_4 = 2a_3 = 2(8) = 16$
$a_5 = 2a_4 = 2(16) = 32$

Step 3: Final Answer:
$a_5 = 32$.


Example 12: Recurrence Relation for Odd Numbers

Problem:
Define the recurrence $a_n = a_{n-1} + 2$ with $a_0 = 1$. Find $a_6$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = a_0 + 2 = 1 + 2 = 3$
$a_2 = a_1 + 2 = 3 + 2 = 5$
$a_3 = a_2 + 2 = 5 + 2 = 7$
$a_4 = a_3 + 2 = 7 + 2 = 9$
$a_5 = a_4 + 2 = 9 + 2 = 11$
$a_6 = a_5 + 2 = 11 + 2 = 13$

Step 3: Final Answer:
$a_6 = 13$.


Example 13: Using the Characteristic Equation

Problem:
Find a solution to the recurrence $a_n = 3a_{n-1} – 2a_{n-2}$ with $a_0 = 0$, $a_1 = 2$.

Answer:

Step 1: Given Data:
$a_0 = 0$, $a_1 = 2$

Step 2: Solution:
The characteristic equation is $r^2 – 3r + 2 = 0$.
Factor to find roots: $(r – 1)(r – 2) = 0$.
Roots are $r_1 = 1$, $r_2 = 2$.
General solution: $a_n = A \cdot 1^n + B \cdot 2^n$.
Using initial conditions:
$0 = A + B$
$2 = A + 2B$
Solving gives $A = 2$, $B = -2$.
Thus, $a_n = 2 – 2 \cdot 2^n$.

Step 3: Final Answer:
$a_n = 2 – 2 \cdot 2^n$.


Example 14: Recurrence Relation for Geometric Series

Problem:
Define $a_n = 2a_{n-1}$ with $a_0 = 1$. Find $a_4$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 2a_0 = 2 \cdot 1 = 2$
$a_2 = 2a_1 = 2 \cdot 2 = 4$
$a_3 = 2a_2 = 2 \cdot 4 = 8$
$a_4 = 2a_3 = 2 \cdot 8 = 16$

Step 3: Final Answer:
$a_4 = 16$.


Example 15: Recurrence Relation for the Sum of First n Integers

Problem:
Define the recurrence $S_n = S_{n-1} + n$ with $S_0 = 0$. Find $S_5$.

Answer:

Step 1: Given Data:
$S_0 = 0$

Step 2: Solution:
$S_1 = S_0 + 1 = 0 + 1 = 1$
$S_2 = S_1 + 2 = 1 + 2 = 3$
$S_3 = S_2 + 3 = 3 + 3 = 6$
$S_4 = S_3 + 4 = 6 + 4 = 10$
$S_5 = S_4 + 5 = 10 + 5 = 15$

Step 3: Final Answer:
$S_5 = 15$.


Example 16: Recurrence Relation for Catalan Numbers

Problem:
Define the recurrence relation for Catalan numbers: $C_n = \sum_{i=0}^{n-1} C_i C_{n-i-1}$ with $C_0 = 1$. Find $C_3$.

Answer:

Step 1: Given Data:
$C_0 = 1$

Step 2: Solution:
$C_1 = C_0 \cdot C_0 = 1 \cdot 1 = 1$
$C_2 = C_0 \cdot C_1 + C_1 \cdot C_0 = 1 \cdot 1 + 1 \cdot 1 = 2$
$C_3 = C_0 \cdot C_2 + C_1 \cdot C_1 + C_2 \cdot C_0 = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$

Step 3: Final Answer:
$C_3 = 5$.


Example 17: Solving a Linear Non-Homogeneous Recurrence

Problem:
Given the recurrence $a_n = 4a_{n-1} + 3$ with $a_0 = 2$, find $a_3$.

Answer:

Step 1: Given Data:
$a_0 = 2$

Step 2: Solution:
$a_1 = 4a_0 + 3 = 4(2) + 3 = 11$
$a_2 = 4a_1 + 3 = 4(11) + 3 = 47$
$a_3 = 4a_2 + 3 = 4(47) + 3 = 191$

Step 3: Final Answer:
$a_3 = 191$.


Example 18: Recurrence Relation for the Sum of Squares

Problem:
Define $S_n = S_{n-1} + n^2$ with $S_0 = 0$. Find $S_4$.

Answer:

Step 1: Given Data:
$S_0 = 0$

Step 2: Solution:
$S_1 = S_0 + 1^2 = 0 + 1 = 1$
$S_2 = S_1 + 2^2 = 1 + 4 = 5$
$S_3 = S_2 + 3^2 = 5 + 9 = 14$
$S_4 = S_3 + 4^2 = 14 + 16 = 30$

Step 3: Final Answer:
$S_4 = 30$.


Example 19: Solving the Tribonacci Sequence

Problem:
Define the recurrence relation $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ with $T_0 = 0$, $T_1 = 1$, $T_2 = 1$. Find $T_4$.

Answer:

Step 1: Given Data:
$T_0 = 0$, $T_1 = 1$, $T_2 = 1$

Step 2: Solution:
$T_3 = T_2 + T_1 + T_0 = 1 + 1 + 0 = 2$
$T_4 = T_3 + T_2 + T_1 = 2 + 1 + 1 = 4$

Step 3: Final Answer:
$T_4 = 4$.


Example 20: Fibonacci and Lucas Connection

Problem:
Prove that $F_n + L_n = L_{n+1}$, where $F_n$ is the Fibonacci number and $L_n$ is the Lucas number.

Answer:

Step 1: Given Data:
$F_n$ is defined as $F_n = F_{n-1} + F_{n-2}$, $L_n = L_{n-1} + L_{n-2}$.

Step 2: Solution:
Base cases:
For $n=0$: $F_0 = 0$, $L_0 = 2 \Rightarrow 0 + 2 = L_1 = 1$.
For $n=1$: $F_1 = 1$, $L_1 = 1 \Rightarrow 1 + 1 = L_2 = 3$.
Assume true for $n = k$:
$F_k + L_k = L_{k+1}$.
Then for $n = k+1$:
$F_{k+1} = F_k + F_{k-1}$, $L_{k+1} = L_k + L_{k-1}$.
Thus, $F_{k+1} + L_{k+1} = (F_k + F_{k-1}) + (L_k + L_{k-1})$.

Step 3: Final Answer:
Proved: $F_n + L_n = L_{n+1}$ for all integers $n$.


Example 21: Recurrence Relation for Exponential Growth

Problem:
Define $a_n = 3a_{n-1} + 2$ with $a_0 = 1$. Find $a_4$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 3a_0 + 2 = 3(1) + 2 = 5$
$a_2 = 3a_1 + 2 = 3(5) + 2 = 17$
$a_3 = 3a_2 + 2 = 3(17) + 2 = 53$
$a_4 = 3a_3 + 2 = 3(53) + 2 = 161$

Step 3: Final Answer:
$a_4 = 161$.


Example 22: Non-linear Recurrence Relation

Problem:
Given the recurrence $a_n = 2a_{n-1}^2 + 1$ with $a_0 = 1$, find $a_3$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 2a_0^2 + 1 = 2(1)^2 + 1 = 3$
$a_2 = 2a_1^2 + 1 = 2(3)^2 + 1 = 19$
$a_3 = 2a_2^2 + 1 = 2(19)^2 + 1 = 723$

Step 3: Final Answer:
$a_3 = 723$.


Example 23: Finding GCD Using Recurrence

Problem:
Use a recurrence relation to compute the GCD of 48 and 18. Define $g(n, m) = g(m, n \mod m)$.

Answer:

Step 1: Given Data:
$n = 48$, $m = 18$

Step 2: Solution:
$g(48, 18) = g(18, 48 \mod 18) = g(18, 12)$
$g(18, 12) = g(12, 18 \mod 12) = g(12, 6)$
$g(12, 6) = g(6, 12 \mod 6) = g(6, 0)$
$g(6, 0) = 6$

Step 3: Final Answer:
The GCD is $6$.


Example 24: Recurrence Relation for Factorial Sequence

Problem:
Define the recurrence $F_n = n \cdot F_{n-1}$ with $F_0 = 1$. Calculate $F_6$.

Answer:

Step 1: Given Data:
$F_0 = 1$

Step 2: Solution:
$F_1 = 1 \cdot F_0 = 1 \cdot 1 = 1$
$F_2 = 2 \cdot F_1 = 2 \cdot 1 = 2$
$F_3 = 3 \cdot F_2 = 3 \cdot 2 = 6$
$F_4 = 4 \cdot F_3 = 4 \cdot 6 = 24$
$F_5 = 5 \cdot F_4 = 5 \cdot 24 = 120$
$F_6 = 6 \cdot F_5 = 6 \cdot 120 = 720$

Step 3: Final Answer:
$F_6 = 720$.


Example 25: Solving a Linear Non-Homogeneous Recurrence

Problem:
Given the recurrence $b_n = 2b_{n-1} + 1$ with $b_0 = 0$, find $b_4$.

Answer:

Step 1: Given Data:
$b_0 = 0$

Step 2: Solution:
$b_1 = 2b_0 + 1 = 2(0) + 1 = 1$
$b_2 = 2b_1 + 1 = 2(1) + 1 = 3$
$b_3 = 2b_2 + 1 = 2(3) + 1 = 7$
$b_4 = 2b_3 + 1 = 2(7) + 1 = 15$

Step 3: Final Answer:
$b_4 = 15$.


Example 26: Recurrence for the Sum of Cubes

Problem:
Define $S_n = S_{n-1} + n^3$ with $S_0 = 0$. Find $S_3$.

Answer:

Step 1: Given Data:
$S_0 = 0$

Step 2: Solution:
$S_1 = S_0 + 1^3 = 0 + 1 = 1$
$S_2 = S_1 + 2^3 = 1 + 8 = 9$
$S_3 = S_2 + 3^3 = 9 + 27 = 36$

Step 3: Final Answer:
$S_3 = 36$.


Example 27: Recurrence Relation for Triangular Numbers

Problem:
Define the recurrence relation for triangular numbers $T_n = T_{n-1} + n$ with $T_0 = 0$. Find $T_5$.

Answer:

Step 1: Given Data:
$T_0 = 0$

Step 2: Solution:
$T_1 = T_0 + 1 = 0 + 1 = 1$
$T_2 = T_1 + 2 = 1 + 2 = 3$
$T_3 = T_2 + 3 = 3 + 3 = 6$
$T_4 = T_3 + 4 = 6 + 4 = 10$
$T_5 = T_4 + 5 = 10 + 5 = 15$

Step 3: Final Answer:
$T_5 = 15$.


Example 28: Recurrence Relation in Pascal’s Triangle

Problem:
Define $C(n, k) = C(n-1, k-1) + C(n-1, k)$ with base cases $C(0, 0) = 1$ and $C(n, 0) = 1$. Calculate $C(4, 2)$.

Answer:

Step 1: Given Data:
$C(0, 0) = 1$, $C(n, 0) = 1$

Step 2: Solution:
$C(1, 0) = 1$
$C(1, 1) = 1$
$C(2, 0) = 1$, $C(2, 1) = C(1, 0) + C(1, 1) = 1 + 1 = 2$
$C(2, 2) = 1$
$C(3, 0) = 1$, $C(3, 1) = C(2, 0) + C(2, 1) = 1 + 2 = 3$
$C(3, 2) = C(2, 1) + C(2, 2) = 2 + 1 = 3$
$C(3, 3) = 1$
$C(4, 0) = 1$, $C(4, 1) = C(3, 0) + C(3, 1) = 1 + 3 = 4$
$C(4, 2) = C(3, 1) + C(3, 2) = 3 + 3 = 6$

Step 3: Final Answer:
$C(4, 2) = 6$.


Example 29: Recurrence for Powers of Two

Problem:
Define $a_n = 2a_{n-1}$ with $a_0 = 1$. Find $a_7$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 2a_0 = 2 \cdot 1 = 2$
$a_2 = 2a_1 = 2 \cdot 2 = 4$
$a_3 = 2a_2 = 2 \cdot 4 = 8$
$a_4 = 2a_3 = 2 \cdot 8 = 16$
$a_5 = 2a_4 = 2 \cdot 16 = 32$
$a_6 = 2a_5 = 2 \cdot 32 = 64$
$a_7 = 2a_6 = 2 \cdot 64 = 128$

Step 3: Final Answer:
$a_7 = 128$.


Example 30: Recurrence Relation for Geometric Series

Problem:
Define $a_n = r a_{n-1}$ with $a_0 = a$. Find $a_4$ for $r = 2$ and $a = 3$.

Answer:

Step 1: Given Data:
$a_0 = 3$, $r = 2$

Step 2: Solution:
$a_1 = 2a_0 = 2 \cdot 3 = 6$
$a_2 = 2a_1 = 2 \cdot 6 = 12$
$a_3 = 2a_2 = 2 \cdot 12 = 24$
$a_4 = 2a_3 = 2 \cdot 24 = 48$

Step 3: Final Answer:
$a_4 = 48$.


Example 31: Recurrence Relation for Fibonacci Sequence

Problem:
Define $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$. Calculate $F_6$.

Answer:

Step 1: Given Data:
$F_0 = 0$, $F_1 = 1$

Step 2: Solution:
$F_2 = F_1 + F_0 = 1 + 0 = 1$
$F_3 = F_2 + F_1 = 1 + 1 = 2$
$F_4 = F_3 + F_2 = 2 + 1 = 3$
$F_5 = F_4 + F_3 = 3 + 2 = 5$
$F_6 = F_5 + F_4 = 5 + 3 = 8$

Step 3: Final Answer:
$F_6 = 8$.


Example 32: Lucas Sequence

Problem:
Define the Lucas numbers by the recurrence $L_n = L_{n-1} + L_{n-2}$ with $L_0 = 2$ and $L_1 = 1$. Find $L_5$.

Answer:

Step 1: Given Data:
$L_0 = 2$, $L_1 = 1$

Step 2: Solution:
$L_2 = L_1 + L_0 = 1 + 2 = 3$
$L_3 = L_2 + L_1 = 3 + 1 = 4$
$L_4 = L_3 + L_2 = 4 + 3 = 7$
$L_5 = L_4 + L_3 = 7 + 4 = 11$

Step 3: Final Answer:
$L_5 = 11$.


Example 33: Recurrence Relation for the Harmonic Sequence

Problem:
Define $H_n = H_{n-1} + \frac{1}{n}$ with $H_1 = 1$. Calculate $H_4$.

Answer:

Step 1: Given Data:
$H_1 = 1$

Step 2: Solution:
$H_2 = H_1 + \frac{1}{2} = 1 + 0.5 = 1.5$
$H_3 = H_2 + \frac{1}{3} = 1.5 + \frac{1}{3} = 1.5 + 0.3333 \approx 1.8333$
$H_4 = H_3 + \frac{1}{4} = 1.8333 + 0.25 \approx 2.0833$

Step 3: Final Answer:
$H_4 \approx 2.0833$.


Example 34: Recurrence Relation for the Number of Subsets

Problem:
Define $a_n = 2a_{n-1}$ with $a_0 = 1$ (the number of subsets of a set with $n$ elements). Find $a_4$.

Answer:

Step 1: Given Data:
$a_0 = 1$

Step 2: Solution:
$a_1 = 2a_0 = 2 \cdot 1 = 2$
$a_2 = 2a_1 = 2 \cdot 2 = 4$
$a_3 = 2a_2 = 2 \cdot 4 = 8$
$a_4 = 2a_3 = 2 \cdot 8 = 16$

Step 3: Final Answer:
$a_4 = 16$.


Example 35: Recurrence Relation for the Collatz Conjecture

Problem:
Define $C(n) = C\left(\frac{n}{2}\right)$ if $n$ is even, otherwise $C(n) = C(3n + 1)$. Start with $C(6)$.

Answer:

Step 1: Given Data:
$n = 6$

Step 2: Solution:
$C(6) = C(3) = C(10) = C(5) = C(16) = C(8) = C(4) = C(2) = C(1)$
We ultimately reach $C(1)$, which ends the sequence.

Step 3: Final Answer:
The sequence from $C(6)$ eventually leads to $C(1)$.


Example 36: Solving a Non-Homogeneous Linear Recurrence

Problem:
Given the relation $a_n = 3a_{n-1} + 4$ with $a_0 = 2$, calculate $a_3$.

Answer:

Step 1: Given Data:
$a_0 = 2$

Step 2: Solution:
$a_1 = 3a_0 + 4 = 3(2) + 4 = 10$
$a_2 = 3a_1 + 4 = 3(10) + 4 = 34$
$a_3 = 3a_2 + 4 = 3(34) + 4 = 106$

Step 3: Final Answer:
$a_3 = 106$.


Example 37: Using Recurrence for Combinations

Problem:
Define $C(n, k) = C(n-1, k-1) + C(n-1, k)$ with base cases $C(n, 0) = 1$. Calculate $C(5, 2)$.

Answer:

Step 1: Given Data:
Base case $C(n, 0) = 1$

Step 2: Solution:
$C(1, 1) = 1$
$C(2, 0) = 1$, $C(2, 1) = C(1, 0) + C(1, 1) = 1 + 1 = 2$
$C(3, 0) = 1$, $C(3, 1) = C(2, 0) + C(2, 1) = 1 + 2 = 3$
$C(4, 0) = 1$, $C(4, 1) = C(3, 0) + C(3, 1) = 1 + 3 = 4$
$C(5, 2) = C(4, 1) + C(4, 2) = 4 + 6 = 10$

Step 3: Final Answer:
$C(5, 2) = 10$.


Example 38: Recurrence Relation in Population Growth

Problem:
Define $P_n = P_{n-1} + 3P_{n-2}$ with initial conditions $P_0 = 1$, $P_1 = 2$. Calculate $P_3$.

Answer:

Step 1: Given Data:
$P_0 = 1$, $P_1 = 2$

Step 2: Solution:
$P_2 = P_1 + 3P_0 = 2 + 3(1) = 5$
$P_3 = P_2 + 3P_1 = 5 + 3(2) = 11$

Step 3: Final Answer:
$P_3 = 11$.


Example 39: Fibonacci Variant

Problem:
Define $F_n = 4F_{n-1} – F_{n-2}$ with base cases $F_0 = 0$, $F_1 = 1$. Find $F_4$.

Answer:

Step 1: Given Data:
$F_0 = 0$, $F_1 = 1$

Step 2: Solution:
$F_2 = 4F_1 – F_0 = 4(1) – 0 = 4$
$F_3 = 4F_2 – F_1 = 4(4) – 1 = 15$
$F_4 = 4F_3 – F_2 = 4(15) – 4 = 56$

Step 3: Final Answer:
$F_4 = 56$.


Example 40: Non-linear Recurrence in Computer Science

Problem:
Define $T(n) = T(n-1) + n^2$ with $T(1) = 1$. Find $T(4)$.

Answer:

Step 1: Given Data:
$T(1) = 1$

Step 2: Solution:
$T(2) = T(1) + 2^2 = 1 + 4 = 5$
$T(3) = T(2) + 3^2 = 5 + 9 = 14$
$T(4) = T(3) + 4^2 = 14 + 16 = 30$

Step 3: Final Answer:
$T(4) = 30$.


Example 41: Recurrence for Total Ways to Arrange Objects

Problem:
Let $A_n = n \cdot A_{n-1}$ with $A_1 = 1$. Find $A_5$.

Answer:

Step 1: Given Data:
$A_1 = 1$

Step 2: Solution:
$A_2 = 2 \cdot A_1 = 2 \cdot 1 = 2$
$A_3 = 3 \cdot A_2 = 3 \cdot 2 = 6$
$A_4 = 4 \cdot A_3 = 4 \cdot 6 = 24$
$A_5 = 5 \cdot A_4 = 5 \cdot 24 = 120$

Step 3: Final Answer:
$A_5 = 120$.


Example 42: Recurrence for Climbing Stairs

Problem:
Define $S_n = S_{n-1} + S_{n-2}$ with base cases $S_0 = 1$, $S_1 = 1$. Find $S_6$.

Answer:

Step 1: Given Data:
$S_0 = 1$, $S_1 = 1$

Step 2: Solution:
$S_2 = S_1 + S_0 = 1 + 1 = 2$
$S_3 = S_2 + S_1 = 2 + 1 = 3$
$S_4 = S_3 + S_2 = 3 + 2 = 5$
$S_5 = S_4 + S_3 = 5 + 3 = 8$
$S_6 = S_5 + S_4 = 8 + 5 = 13$

Step 3: Final Answer:
$S_6 = 13$.


Example 43: Recurrence for String Length

Problem:
Define $L_n = 2L_{n-1} + 1$ with $L_0 = 1$. Find $L_4$.

Answer:

Step 1: Given Data:
$L_0 = 1$

Step 2: Solution:
$L_1 = 2L_0 + 1 = 2 \cdot 1 + 1 = 3$
$L_2 = 2L_1 + 1 = 2 \cdot 3 + 1 = 7$
$L_3 = 2L_2 + 1 = 2 \cdot 7 + 1 = 15$
$L_4 = 2L_3 + 1 = 2 \cdot 15 + 1 = 31$

Step 3: Final Answer:
$L_4 = 31$.


Example 44: Recurrence for Geometric Series Sum

Problem:
Define $S_n = 3S_{n-1} + 2$ with $S_0 = 0$. Find $S_3$.

Answer:

Step 1: Given Data:
$S_0 = 0$

Step 2: Solution:
$S_1 = 3S_0 + 2 = 3 \cdot 0 + 2 = 2$
$S_2 = 3S_1 + 2 = 3 \cdot 2 + 2 = 8$
$S_3 = 3S_2 + 2 = 3 \cdot 8 + 2 = 26$

Step 3: Final Answer:
$S_3 = 26$.


Example 45: Recurrence for Sequence Defined by Sums

Problem:
Define $b_n = b_{n-1} + b_{n-2}$ with base cases $b_0 = 1$, $b_1 = 1$. Calculate $b_5$.

Answer:

Step 1: Given Data:
$b_0 = 1$, $b_1 = 1$

Step 2: Solution:
$b_2 = b_1 + b_0 = 1 + 1 = 2$
$b_3 = b_2 + b_1 = 2 + 1 = 3$
$b_4 = b_3 + b_2 = 3 + 2 = 5$
$b_5 = b_4 + b_3 = 5 + 3 = 8$

Step 3: Final Answer:
$b_5 = 8$.


Example 46: Recurrence for Polynomial Evaluation

Problem:
Define $P(n) = P(n-1) + 2n + 1$ with $P(0) = 0$. Find $P(3)$.

Answer:

Step 1: Given Data:
$P(0) = 0$

Step 2: Solution:
$P(1) = P(0) + 2(1) + 1 = 0 + 2 + 1 = 3$
$P(2) = P(1) + 2(2) + 1 = 3 + 4 + 1 = 8$
$P(3) = P(2) + 2(3) + 1 = 8 + 6 + 1 = 15$

Step 3: Final Answer:
$P(3) = 15$.


Example 47: Recurrence for Counting Ways

Problem:
Define $C(n) = C(n-1) + C(n-2)$ with base cases $C(1) = 1$, $C(2) = 2$. Find $C(6)$.

Answer:

Step 1: Given Data:
$C(1) = 1$, $C(2) = 2$

Step 2: Solution:
$C(3) = C(2) + C(1) = 2 + 1 = 3$
$C(4) = C(3) + C(2) = 3 + 2 = 5$
$C(5) = C(4) + C(3) = 5 + 3 = 8$
$C(6) = C(5) + C(4) = 8 + 5 = 13$

Step 3: Final Answer:
$C(6) = 13$.


Example 48: Recurrence for Arithmetic Sequence

Problem:
Define $A_n = A_{n-1} + 5$ with $A_0 = 10$. Find $A_4$.

Answer:

Step 1: Given Data:
$A_0 = 10$

Step 2: Solution:
$A_1 = A_0 + 5 = 10 + 5 = 15$
$A_2 = A_1 + 5 = 15 + 5 = 20$
$A_3 = A_2 + 5 = 20 + 5 = 25$
$A_4 = A_3 + 5 = 25 + 5 = 30$

Step 3: Final Answer:
$A_4 = 30$.


Example 49: Recurrence for Fibonacci-Like Sequence

Problem:
Define $X_n = 4X_{n-1} + 3X_{n-2}$ with $X_0 = 2$, $X_1 = 3$. Calculate $X_3$.

Answer:

Step 1: Given Data:
$X_0 = 2$, $X_1 = 3$

Step 2: Solution:
$X_2 = 4X_1 + 3X_0 = 4(3) + 3(2) = 12 + 6 = 18$
$X_3 = 4X_2 + 3X_1 = 4(18) + 3(3) = 72 + 9 = 81$

Step 3: Final Answer:
$X_3 = 81$.


Example 50: Recurrence for Counting Permutations

Problem:
Define $P(n) = n \cdot P(n-1)$ with $P(0) = 1$. Find $P(4)$.

Answer:

Step 1: Given Data:
$P(0) = 1$

Step 2: Solution:
$P(1) = 1 \cdot P(0) = 1 \cdot 1 = 1$
$P(2) = 2 \cdot P(1) = 2 \cdot 1 = 2$
$P(3) = 3 \cdot P(2) = 3 \cdot 2 = 6$
$P(4) = 4 \cdot P(3) = 4 \cdot 6 = 24$

Step 3: Final Answer:
$P(4) = 24$.


Example 51: Recurrence for Tiling Problems

Problem:
Define $T(n) = T(n-1) + T(n-2)$ with base cases $T(0) = 1$, $T(1) = 1$. Calculate $T(5)$.

Answer:

Step 1: Given Data:
$T(0) = 1$, $T(1) = 1$

Step 2: Solution:
$T(2) = T(1) + T(0) = 1 + 1 = 2$
$T(3) = T(2) + T(1) = 2 + 1 = 3$
$T(4) = T(3) + T(2) = 3 + 2 = 5$
$T(5) = T(4) + T(3) = 5 + 3 = 8$

Step 3: Final Answer:
$T(5) = 8$.


Example 52: Recurrence for Exponential Growth

Problem:
Define $N(n) = 3N(n-1)$ with base case $N(0) = 1$. Find $N(4)$.

Answer:

Step 1: Given Data:
$N(0) = 1$

Step 2: Solution:
$N(1) = 3N(0) = 3 \cdot 1 = 3$
$N(2) = 3N(1) = 3 \cdot 3 = 9$
$N(3) = 3N(2) = 3 \cdot 9 = 27$
$N(4) = 3N(3) = 3 \cdot 27 = 81$

Step 3: Final Answer:
$N(4) = 81$.


Example 53: Recurrence Relation for Game Scoring

Problem:
Define $S_n = S_{n-1} + 10$ with $S_0 = 0$. Find $S_5$.

Answer:

Step 1: Given Data:
$S_0 = 0$

Step 2: Solution:
$S_1 = S_0 + 10 = 0 + 10 = 10$
$S_2 = S_1 + 10 = 10 + 10 = 20$
$S_3 = S_2 + 10 = 20 + 10 = 30$
$S_4 = S_3 + 10 = 30 + 10 = 40$
$S_5 = S_4 + 10 = 40 + 10 = 50$

Step 3: Final Answer:
$S_5 = 50$.


Example 54: Recurrence for Investment Growth

Problem:
Define $A_n = A_{n-1} \times (1 + r)$ with $A_0 = P$ (initial investment). Find $A_3$ with $r = 0.05$ and $P = 1000$.

Answer:

Step 1: Given Data:
$A_0 = 1000$, $r = 0.05$

Step 2: Solution:
$A_1 = A_0 \times (1 + r) = 1000 \times 1.05 = 1050$
$A_2 = A_1 \times (1 + r) = 1050 \times 1.05 = 1102.5$
$A_3 = A_2 \times (1 + r) = 1102.5 \times 1.05 = 1157.625$

Step 3: Final Answer:
$A_3 \approx 1157.63$.


Example 55: Recurrence for Paths in a Grid

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(1) = 1$, $P(2) = 2$. Calculate $P(6)$.

Answer:

Step 1: Given Data:
$P(1) = 1$, $P(2) = 2$

Step 2: Solution:
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$
$P(6) = P(5) + P(4) = 8 + 5 = 13$

Step 3: Final Answer:
$P(6) = 13$.


Example 56: Recurrence for Fibonacci-Like Sequence

Problem:
Define $F_n = 2F_{n-1} + F_{n-2}$ with $F_0 = 1$, $F_1 = 1$. Calculate $F_5$.

Answer:

Step 1: Given Data:
$F_0 = 1$, $F_1 = 1$

Step 2: Solution:
$F_2 = 2F_1 + F_0 = 2 \cdot 1 + 1 = 3$
$F_3 = 2F_2 + F_1 = 2 \cdot 3 + 1 = 7$
$F_4 = 2F_3 + F_2 = 2 \cdot 7 + 3 = 17$
$F_5 = 2F_4 + F_3 = 2 \cdot 17 + 7 = 41$

Step 3: Final Answer:
$F_5 = 41$.


Example 57: Recurrence for Divisor Count

Problem:
Define $D(n) = D(n-1) + 1$ with $D(1) = 1$. Find $D(5)$.

Answer:

Step 1: Given Data:
$D(1) = 1$

Step 2: Solution:
$D(2) = D(1) + 1 = 1 + 1 = 2$
$D(3) = D(2) + 1 = 2 + 1 = 3$
$D(4) = D(3) + 1 = 3 + 1 = 4$
$D(5) = D(4) + 1 = 4 + 1 = 5$

Step 3: Final Answer:
$D(5) = 5$.


Example 58: Recurrence for Bell Numbers

Problem:
Define $B(n) = \sum_{k=0}^{n-1} C(n-1, k) B(k)$ with base case $B(0) = 1$. Calculate $B(3)$.

Answer:

Step 1: Given Data:
$B(0) = 1$

Step 2: Solution:
$B(1) = C(0, 0)B(0) = 1 \cdot 1 = 1$
$B(2) = C(1, 0)B(0) + C(1, 1)B(1) = 1 \cdot 1 + 1 \cdot 1 = 2$
$B(3) = C(2, 0)B(0) + C(2, 1)B(1) + C(2, 2)B(2) = 1 \cdot 1 + 2 \cdot 1 + 1 \cdot 2 = 5$

Step 3: Final Answer:
$B(3) = 5$.


Example 59: Recurrence for Total Ways to Arrange Puzzles

Problem:
Define $A_n = 2A_{n-1} + 1$ with base case $A_0 = 1$. Find $A_4$.

Answer:

Step 1: Given Data:
$A_0 = 1$

Step 2: Solution:
$A_1 = 2A_0 + 1 = 2 \cdot 1 + 1 = 3$
$A_2 = 2A_1 + 1 = 2 \cdot 3 + 1 = 7$
$A_3 = 2A_2 + 1 = 2 \cdot 7 + 1 = 15$
$A_4 = 2A_3 + 1 = 2 \cdot 15 + 1 = 31$

Step 3: Final Answer:
$A_4 = 31$.


Example 60: Recurrence for Maximum Subarray Sum

Problem:
Define $M(n) = M(n-1) + a_n$ with base case $M(0) = 0$. Find $M(3)$ with $a_1 = 3$, $a_2 = 5$, $a_3 = -2$.

Answer:

Step 1: Given Data:
$M(0) = 0$, $a_1 = 3$, $a_2 = 5$, $a_3 = -2$

Step 2: Solution:
$M(1) = M(0) + a_1 = 0 + 3 = 3$
$M(2) = M(1) + a_2 = 3 + 5 = 8$
$M(3) = M(2) + a_3 = 8 – 2 = 6$

Step 3: Final Answer:
$M(3) = 6$.


Example 61: Recurrence for Path Counting in a Grid

Problem:
Define $C(n, m) = C(n-1, m) + C(n, m-1)$ with base cases $C(0, m) = 1$ and $C(n, 0) = 1$. Calculate $C(3, 2)$.

Answer:

Step 1: Given Data:
Base cases $C(0, m) = 1$, $C(n, 0) = 1$

Step 2: Solution:
$C(1, 1) = C(0, 1) + C(1, 0) = 1 + 1 = 2$
$C(2, 1) = C(1, 1) + C(2, 0) = 2 + 1 = 3$
$C(3, 1) = C(2, 1) + C(3, 0) = 3 + 1 = 4$
$C(2, 2) = C(1, 2) + C(2, 1) = 2 + 3 = 5$
$C(3, 2) = C(2, 2) + C(3, 1) = 5 + 4 = 9$

Step 3: Final Answer:
$C(3, 2) = 9$.


Example 62: Recurrence for Catalan Numbers

Problem:
Define $C(n) = \sum_{i=0}^{n-1} C(i)C(n-i-1)$ with $C(0) = 1$. Calculate $C(3)$.

Answer:

Step 1: Given Data:
$C(0) = 1$

Step 2: Solution:
$C(1) = C(0)C(0) = 1 \cdot 1 = 1$
$C(2) = C(0)C(1) + C(1)C(0) = 1 \cdot 1 + 1 \cdot 1 = 2$
$C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$

Step 3: Final Answer:
$C(3) = 5$.


Example 63: Recurrence for Factorial Growth

Problem:
Define $F(n) = n \cdot F(n-1)$ with $F(0) = 1$. Calculate $F(5)$.

Answer:

Step 1: Given Data:
$F(0) = 1$

Step 2: Solution:
$F(1) = 1 \cdot F(0) = 1$
$F(2) = 2 \cdot F(1) = 2 \cdot 1 = 2$
$F(3) = 3 \cdot F(2) = 3 \cdot 2 = 6$
$F(4) = 4 \cdot F(3) = 4 \cdot 6 = 24$
$F(5) = 5 \cdot F(4) = 5 \cdot 24 = 120$

Step 3: Final Answer:
$F(5) = 120$.


Example 64: Recurrence for Coin Change Problem

Problem:
Define $C(n) = C(n-1) + C(n-2)$ with base cases $C(0) = 1$, $C(1) = 1$. Calculate $C(4)$.

Answer:

Step 1: Given Data:
$C(0) = 1$, $C(1) = 1$

Step 2: Solution:
$C(2) = C(1) + C(0) = 1 + 1 = 2$
$C(3) = C(2) + C(1) = 2 + 1 = 3$
$C(4) = C(3) + C(2) = 3 + 2 = 5$

Step 3: Final Answer:
$C(4) = 5$.


Example 65: Recurrence for Optimal Game Strategy

Problem:
Define $G(n) = G(n-1) + G(n-2)$ with base cases $G(1) = 1$, $G(2) = 2$. Find $G(5)$.

Answer:

Step 1: Given Data:
$G(1) = 1$, $G(2) = 2$

Step 2: Solution:
$G(3) = G(2) + G(1) = 2 + 1 = 3$
$G(4) = G(3) + G(2) = 3 + 2 = 5$
$G(5) = G(4) + G(3) = 5 + 3 = 8$

Step 3: Final Answer:
$G(5) = 8$.


Example 66: Recurrence for Combinatorial Counting

Problem:
Define $C(n, k) = C(n-1, k-1) + C(n-1, k)$ with base case $C(0, 0) = 1$. Calculate $C(4, 2)$.

Answer:

Step 1: Given Data:
Base case $C(0, 0) = 1$

Step 2: Solution:
$C(1, 0) = 1$, $C(1, 1) = 1$
$C(2, 0) = 1$, $C(2, 1) = 2$, $C(2, 2) = 1$
$C(3, 0) = 1$, $C(3, 1) = 3$, $C(3, 2) = 3$
$C(4, 0) = 1$, $C(4, 1) = 4$, $C(4, 2) = 6$

Step 3: Final Answer:
$C(4, 2) = 6$.


Example 67: Recurrence for Height of Trees

Problem:
Define $H(n) = H(n-1) + H(n-2)$ with base cases $H(0) = 1$, $H(1) = 1$. Calculate $H(6)$.

Answer:

Step 1: Given Data:
$H(0) = 1$, $H(1) = 1$

Step 2: Solution:
$H(2) = H(1) + H(0) = 1 + 1 = 2$
$H(3) = H(2) + H(1) = 2 + 1 = 3$
$H(4) = H(3) + H(2) = 3 + 2 = 5$
$H(5) = H(4) + H(3) = 5 + 3 = 8$
$H(6) = H(5) + H(4) = 8 + 5 = 13$

Step 3: Final Answer:
$H(6) = 13$.


Example 68: Recurrence for Maximum Path in Grid

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(1) = 1$, $P(2) = 2$. Find $P(5)$.

Answer:

Step 1: Given Data:
$P(1) = 1$, $P(2) = 2$

Step 2: Solution:
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$

Step 3: Final Answer:
$P(5) = 8$.


Example 69: Recurrence for Arranging Objects

Problem:
Define $A(n) = n \cdot A(n-1)$ with base case $A(1) = 1$. Calculate $A(4)$.

Answer:

Step 1: Given Data:
$A(1) = 1$

Step 2: Solution:
$A(2) = 2 \cdot A(1) = 2 \cdot 1 = 2$
$A(3) = 3 \cdot A(2) = 3 \cdot 2 = 6$
$A(4) = 4 \cdot A(3) = 4 \cdot 6 = 24$

Step 3: Final Answer:
$A(4) = 24$.


Example 70: Recurrence for Quadratic Growth

Problem:
Define $Q(n) = 3Q(n-1) + 1$ with base case $Q(0) = 0$. Find $Q(3)$.

Answer:

Step 1: Given Data:
$Q(0) = 0$

Step 2: Solution:
$Q(1) = 3Q(0) + 1 = 3 \cdot 0 + 1 = 1$
$Q(2) = 3Q(1) + 1 = 3 \cdot 1 + 1 = 4$
$Q(3) = 3Q(2) + 1 = 3 \cdot 4 + 1 = 13$

Step 3: Final Answer:
$Q(3) = 13$.


Example 71: Recurrence for Sums of Powers

Problem:
Define $S(n) = S(n-1) + n^3$ with base case $S(0) = 0$. Find $S(3)$.

Answer:

Step 1: Given Data:
$S(0) = 0$

Step 2: Solution:
$S(1) = S(0) + 1^3 = 0 + 1 = 1$
$S(2) = S(1) + 2^3 = 1 + 8 = 9$
$S(3) = S(2) + 3^3 = 9 + 27 = 36$

Step 3: Final Answer:
$S(3) = 36$.


Example 72: Recurrence for Binary Trees

Problem:
Define $T(n) = 2T(n-1)$ with base case $T(0) = 1$. Find $T(4)$.

Answer:

Step 1: Given Data:
$T(0) = 1$

Step 2: Solution:
$T(1) = 2T(0) = 2 \cdot 1 = 2$
$T(2) = 2T(1) = 2 \cdot 2 = 4$
$T(3) = 2T(2) = 2 \cdot 4 = 8$
$T(4) = 2T(3) = 2 \cdot 8 = 16$

Step 3: Final Answer:
$T(4) = 16$.


Example 73: Recurrence for Sequence Defined by Fibonacci-Like Relation

Problem:
Define $F(n) = 2F(n-1) + 3F(n-2)$ with base cases $F(0) = 1$, $F(1) = 1$. Calculate $F(3)$.

Answer:

Step 1: Given Data:
$F(0) = 1$, $F(1) = 1$

Step 2: Solution:
$F(2) = 2F(1) + 3F(0) = 2 \cdot 1 + 3 \cdot 1 = 5$
$F(3) = 2F(2) + 3F(1) = 2 \cdot 5 + 3 \cdot 1 = 10 + 3 = 13$

Step 3: Final Answer:
$F(3) = 13$.


Example 74: Recurrence for Count of Ways to Climb Stairs

Problem:
Define $C(n) = C(n-1) + C(n-2)$ with base cases $C(0) = 1$, $C(1) = 1$. Find $C(7)$.

Answer:

Step 1: Given Data:
$C(0) = 1$, $C(1) = 1$

Step 2: Solution:
$C(2) = C(1) + C(0) = 1 + 1 = 2$
$C(3) = C(2) + C(1) = 2 + 1 = 3$
$C(4) = C(3) + C(2) = 3 + 2 = 5$
$C(5) = C(4) + C(3) = 5 + 3 = 8$
$C(6) = C(5) + C(4) = 8 + 5 = 13$
$C(7) = C(6) + C(5) = 13 + 8 = 21$

Step 3: Final Answer:
$C(7) = 21$.


Example 75: Recurrence for Count of Ways to Arrange Items

Problem:
Define $W(n) = W(n-1) + W(n-2)$ with base cases $W(0) = 1$, $W(1) = 1$. Find $W(8)$.

Answer:

Step 1: Given Data:
$W(0) = 1$, $W(1) = 1$

Step 2: Solution:
$W(2) = W(1) + W(0) = 1 + 1 = 2$
$W(3) = W(2) + W(1) = 2 + 1 = 3$
$W(4) = W(3) + W(2) = 3 + 2 = 5$
$W(5) = W(4) + W(3) = 5 + 3 = 8$
$W(6) = W(5) + W(4) = 8 + 5 = 13$
$W(7) = W(6) + W(5) = 13 + 8 = 21$
$W(8) = W(7) + W(6) = 21 + 13 = 34$

Step 3: Final Answer:
$W(8) = 34$.


Example 76: Recurrence for Squares in a Series

Problem:
Define $S(n) = S(n-1) + n^2$ with base case $S(0) = 0$. Find $S(4)$.

Answer:

Step 1: Given Data:
$S(0) = 0$

Step 2: Solution:
$S(1) = S(0) + 1^2 = 0 + 1 = 1$
$S(2) = S(1) + 2^2 = 1 + 4 = 5$
$S(3) = S(2) + 3^2 = 5 + 9 = 14$
$S(4) = S(3) + 4^2 = 14 + 16 = 30$

Step 3: Final Answer:
$S(4) = 30$.


Example 77: Recurrence for Game Scores

Problem:
Define $S(n) = S(n-1) + S(n-2)$ with base cases $S(1) = 1$, $S(2) = 3$. Calculate $S(6)$.

Answer:

Step 1: Given Data:
$S(1) = 1$, $S(2) = 3$

Step 2: Solution:
$S(3) = S(2) + S(1) = 3 + 1 = 4$
$S(4) = S(3) + S(2) = 4 + 3 = 7$
$S(5) = S(4) + S(3) = 7 + 4 = 11$
$S(6) = S(5) + S(4) = 11 + 7 = 18$

Step 3: Final Answer:
$S(6) = 18$.


Example 78: Recurrence for Total Count of Options

Problem:
Define $O(n) = O(n-1) + O(n-2)$ with base cases $O(0) = 1$, $O(1) = 2$. Find $O(5)$.

Answer:

Step 1: Given Data:
$O(0) = 1$, $O(1) = 2$

Step 2: Solution:
$O(2) = O(1) + O(0) = 2 + 1 = 3$
$O(3) = O(2) + O(1) = 3 + 2 = 5$
$O(4) = O(3) + O(2) = 5 + 3 = 8$
$O(5) = O(4) + O(3) = 8 + 5 = 13$

Step 3: Final Answer:
$O(5) = 13$.


Example 79: Recurrence for Climbing Stairs Problem

Problem:
Define $S(n) = S(n-1) + S(n-2)$ with base cases $S(0) = 1$, $S(1) = 1$. Calculate $S(9)$.

Answer:

Step 1: Given Data:
$S(0) = 1$, $S(1) = 1$

Step 2: Solution:
$S(2) = S(1) + S(0) = 1 + 1 = 2$
$S(3) = S(2) + S(1) = 2 + 1 = 3$
$S(4) = S(3) + S(2) = 3 + 2 = 5$
$S(5) = S(4) + S(3) = 5 + 3 = 8$
$S(6) = S(5) + S(4) = 8 + 5 = 13$
$S(7) = S(6) + S(5) = 13 + 8 = 21$
$S(8) = S(7) + S(6) = 21 + 13 = 34$
$S(9) = S(8) + S(7) = 34 + 21 = 55$

Step 3: Final Answer:
$S(9) = 55$.


Example 80: Recurrence for String Combinations

Problem:
Define $C(n) = C(n-1) + C(n-2)$ with base cases $C(1) = 1$, $C(2) = 2$. Find $C(6)$.

Answer:

Step 1: Given Data:
$C(1) = 1$, $C(2) = 2$

Step 2: Solution:
$C(3) = C(2) + C(1) = 2 + 1 = 3$
$C(4) = C(3) + C(2) = 3 + 2 = 5$
$C(5) = C(4) + C(3) = 5 + 3 = 8$
$C(6) = C(5) + C(4) = 8 + 5 = 13$

Step 3: Final Answer:
$C(6) = 13$.


Example 81: Recurrence for Path Counting in a Grid

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(0) = 1$, $P(1) = 1$. Find $P(8)$.

Answer:

Step 1: Given Data:
$P(0) = 1$, $P(1) = 1$

Step 2: Solution:
$P(2) = P(1) + P(0) = 1 + 1 = 2$
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$
$P(6) = P(5) + P(4) = 8 + 5 = 13$
$P(7) = P(6) + P(5) = 13 + 8 = 21$
$P(8) = P(7) + P(6) = 21 + 13 = 34$

Step 3: Final Answer:
$P(8) = 34$.


Example 82: Recurrence for Total Combinations

Problem:
Define $C(n, k) = C(n-1, k-1) + C(n-1, k)$ with base case $C(0, 0) = 1$. Calculate $C(5, 3)$.

Answer:

Step 1: Given Data:
Base case $C(0, 0) = 1$

Step 2: Solution:
$C(1, 0) = 1$, $C(1, 1) = 1$
$C(2, 0) = 1$, $C(2, 1) = 2$, $C(2, 2) = 1$
$C(3, 0) = 1$, $C(3, 1) = 3$, $C(3, 2) = 3$, $C(3, 3) = 1$
$C(4, 0) = 1$, $C(4, 1) = 4$, $C(4, 2) = 6$, $C(4, 3) = 4$, $C(4, 4) = 1$
$C(5, 0) = 1$, $C(5, 1) = 5$, $C(5, 2) = 10$, $C(5, 3) = 10$, $C(5, 4) = 5$, $C(5, 5) = 1$

Step 3: Final Answer:
$C(5, 3) = 10$.


Example 83: Recurrence for Count of Unique Paths

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(0) = 1$, $P(1) = 1$. Find $P(10)$.

Answer:

Step 1: Given Data:
$P(0) = 1$, $P(1) = 1$

Step 2: Solution:
$P(2) = P(1) + P(0) = 1 + 1 = 2$
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$
$P(6) = P(5) + P(4) = 8 + 5 = 13$
$P(7) = P(6) + P(5) = 13 + 8 = 21$
$P(8) = P(7) + P(6) = 21 + 13 = 34$
$P(9) = P(8) + P(7) = 34 + 21 = 55$
$P(10) = P(9) + P(8) = 55 + 34 = 89$

Step 3: Final Answer:
$P(10) = 89$.


Example 84: Recurrence for Count of Ways to Select Objects

Problem:
Define $C(n, k) = C(n-1, k-1) + C(n-1, k)$ with base case $C(0, 0) = 1$. Calculate $C(6, 3)$.

Answer:

Step 1: Given Data:
Base case $C(0, 0) = 1$

Step 2: Solution:
$C(1, 0) = 1$, $C(1, 1) = 1$
$C(2, 0) = 1$, $C(2, 1) = 2$, $C(2, 2) = 1$
$C(3, 0) = 1$, $C(3, 1) = 3$, $C(3, 2) = 3$, $C(3, 3) = 1$
$C(4, 0) = 1$, $C(4, 1) = 4$, $C(4, 2) = 6$, $C(4, 3) = 4$, $C(4, 4) = 1$
$C(5, 0) = 1$, $C(5, 1) = 5$, $C(5, 2) = 10$, $C(5, 3) = 10$, $C(5, 4) = 5$, $C(5, 5) = 1$
$C(6, 0) = 1$, $C(6, 1) = 6$, $C(6, 2) = 15$, $C(6, 3) = 20$, $C(6, 4) = 15$, $C(6, 5) = 6$, $C(6, 6) = 1$

Step 3: Final Answer:
$C(6, 3) = 20$.


Example 85: Recurrence for Growth in Population

Problem:
Define $P(n) = 2P(n-1) + 1$ with base case $P(0) = 1$. Find $P(5)$.

Answer:

Step 1: Given Data:
$P(0) = 1$

Step 2: Solution:
$P(1) = 2P(0) + 1 = 2 \cdot 1 + 1 = 3$
$P(2) = 2P(1) + 1 = 2 \cdot 3 + 1 = 7$
$P(3) = 2P(2) + 1 = 2 \cdot 7 + 1 = 15$
$P(4) = 2P(3) + 1 = 2 \cdot 15 + 1 = 31$
$P(5) = 2P(4) + 1 = 2 \cdot 31 + 1 = 63$

Step 3: Final Answer:
$P(5) = 63$.


Example 86: Recurrence for Count of Distinct Permutations

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(1) = 1$, $P(2) = 2$. Find $P(8)$.

Answer:

Step 1: Given Data:
$P(1) = 1$, $P(2) = 2$

Step 2: Solution:
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$
$P(6) = P(5) + P(4) = 8 + 5 = 13$
$P(7) = P(6) + P(5) = 13 + 8 = 21$
$P(8) = P(7) + P(6) = 21 + 13 = 34$

Step 3: Final Answer:
$P(8) = 34$.


Example 87: Recurrence for Sums of Integers

Problem:
Define $S(n) = S(n-1) + n$ with base case $S(0) = 0$. Find $S(5)$.

Answer:

Step 1: Given Data:
$S(0) = 0$

Step 2: Solution:
$S(1) = S(0) + 1 = 0 + 1 = 1$
$S(2) = S(1) + 2 = 1 + 2 = 3$
$S(3) = S(2) + 3 = 3 + 3 = 6$
$S(4) = S(3) + 4 = 6 + 4 = 10$
$S(5) = S(4) + 5 = 10 + 5 = 15$

Step 3: Final Answer:
$S(5) = 15$.


Example 88: Recurrence for Count of Non-Negative Solutions

Problem:
Define $C(n) = C(n-1) + C(n-2)$ with base cases $C(0) = 1$, $C(1) = 1$. Find $C(12)$.

Answer:

Step 1: Given Data:
$C(0) = 1$, $C(1) = 1$

Step 2: Solution:
$C(2) = C(1) + C(0) = 1 + 1 = 2$
$C(3) = C(2) + C(1) = 2 + 1 = 3$
$C(4) = C(3) + C(2) = 3 + 2 = 5$
$C(5) = C(4) + C(3) = 5 + 3 = 8$
$C(6) = C(5) + C(4) = 8 + 5 = 13$
$C(7) = C(6) + C(5) = 13 + 8 = 21$
$C(8) = C(7) + C(6) = 21 + 13 = 34$
$C(9) = C(8) + C(7) = 34 + 21 = 55$
$C(10) = C(9) + C(8) = 55 + 34 = 89$
$C(11) = C(10) + C(9) = 89 + 55 = 144$
$C(12) = C(11) + C(10) = 144 + 89 = 233$

Step 3: Final Answer:
$C(12) = 233$.


Example 89: Recurrence for Fibonacci Sequence

Problem:
Define $F(n) = F(n-1) + F(n-2)$ with base cases $F(0) = 0$, $F(1) = 1$. Calculate $F(10)$.

Answer:

Step 1: Given Data:
$F(0) = 0$, $F(1) = 1$

Step 2: Solution:
$F(2) = F(1) + F(0) = 1 + 0 = 1$
$F(3) = F(2) + F(1) = 1 + 1 = 2$
$F(4) = F(3) + F(2) = 2 + 1 = 3$
$F(5) = F(4) + F(3) = 3 + 2 = 5$
$F(6) = F(5) + F(4) = 5 + 3 = 8$
$F(7) = F(6) + F(5) = 8 + 5 = 13$
$F(8) = F(7) + F(6) = 13 + 8 = 21$
$F(9) = F(8) + F(7) = 21 + 13 = 34$
$F(10) = F(9) + F(8) = 34 + 21 = 55$

Step 3: Final Answer:
$F(10) = 55$.


Example 90: Recurrence for Count of Unique Binary Trees

Problem:
Define $B(n) = \sum_{i=0}^{n-1} B(i)B(n-i-1)$ with base case $B(0) = 1$. Calculate $B(4)$.

Answer:

Step 1: Given Data:
$B(0) = 1$

Step 2: Solution:
$B(1) = B(0)B(0) = 1 \cdot 1 = 1$
$B(2) = B(0)B(1) + B(1)B(0) = 1 \cdot 1 + 1 \cdot 1 = 2$
$B(3) = B(0)B(2) + B(1)B(1) + B(2)B(0) = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$
$B(4) = B(0)B(3) + B(1)B(2) + B(2)B(1) + B(3)B(0) = 1 \cdot 5 + 1 \cdot 2 + 2 \cdot 1 + 5 \cdot 1 = 14$

Step 3: Final Answer:
$B(4) = 14$.


Example 91: Recurrence for Maximum Sum Subsequence

Problem:
Define $M(n) = M(n-1) + a_n$ with base case $M(0) = 0$. Find $M(4)$ with $a_1 = 2$, $a_2 = 3$, $a_3 = 5$, $a_4 = 7$.

Answer:

Step 1: Given Data:
$M(0) = 0$, $a_1 = 2$, $a_2 = 3$, $a_3 = 5$, $a_4 = 7$

Step 2: Solution:
$M(1) = M(0) + a_1 = 0 + 2 = 2$
$M(2) = M(1) + a_2 = 2 + 3 = 5$
$M(3) = M(2) + a_3 = 5 + 5 = 10$
$M(4) = M(3) + a_4 = 10 + 7 = 17$

Step 3: Final Answer:
$M(4) = 17$.


Example 92: Recurrence for Count of Triangular Numbers

Problem:
Define $T(n) = T(n-1) + n$ with base case $T(0) = 0$. Find $T(5)$.

Answer:

Step 1: Given Data:
$T(0) = 0$

Step 2: Solution:
$T(1) = T(0) + 1 = 0 + 1 = 1$
$T(2) = T(1) + 2 = 1 + 2 = 3$
$T(3) = T(2) + 3 = 3 + 3 = 6$
$T(4) = T(3) + 4 = 6 + 4 = 10$
$T(5) = T(4) + 5 = 10 + 5 = 15$

Step 3: Final Answer:
$T(5) = 15$.


Example 93: Recurrence for Count of Paths in a Maze

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(0) = 1$, $P(1) = 1$. Find $P(11)$.

Answer:

Step 1: Given Data:
$P(0) = 1$, $P(1) = 1$

Step 2: Solution:
$P(2) = P(1) + P(0) = 1 + 1 = 2$
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$
$P(6) = P(5) + P(4) = 8 + 5 = 13$
$P(7) = P(6) + P(5) = 13 + 8 = 21$
$P(8) = P(7) + P(6) = 21 + 13 = 34$
$P(9) = P(8) + P(7) = 34 + 21 = 55$
$P(10) = P(9) + P(8) = 55 + 34 = 89$
$P(11) = P(10) + P(9) = 89 + 55 = 144$

Step 3: Final Answer:
$P(11) = 144$.


Example 94: Recurrence for Count of Ways to Form Numbers

Problem:
Define $F(n) = F(n-1) + F(n-2)$ with base cases $F(0) = 0$, $F(1) = 1$. Find $F(12)$.

Answer:

Step 1: Given Data:
$F(0) = 0$, $F(1) = 1$

Step 2: Solution:
$F(2) = F(1) + F(0) = 1 + 0 = 1$
$F(3) = F(2) + F(1) = 1 + 1 = 2$
$F(4) = F(3) + F(2) = 2 + 1 = 3$
$F(5) = F(4) + F(3) = 3 + 2 = 5$
$F(6) = F(5) + F(4) = 5 + 3 = 8$
$F(7) = F(6) + F(5) = 8 + 5 = 13$
$F(8) = F(7) + F(6) = 13 + 8 = 21$
$F(9) = F(8) + F(7) = 21 + 13 = 34$
$F(10) = F(9) + F(8) = 34 + 21 = 55$
$F(11) = F(10) + F(9) = 55 + 34 = 89$
$F(12) = F(11) + F(10) = 89 + 55 = 144$

Step 3: Final Answer:
$F(12) = 144$.


Example 95: Recurrence for Count of Non-attacking Queens

Problem:
Define $Q(n) = \sum_{i=0}^{n-1} Q(i)Q(n-i-1)$ with base case $Q(0) = 1$. Calculate $Q(5)$.

Answer:

Step 1: Given Data:
$Q(0) = 1$

Step 2: Solution:
$Q(1) = Q(0)Q(0) = 1 \cdot 1 = 1$
$Q(2) = Q(0)Q(1) + Q(1)Q(0) = 1 \cdot 1 + 1 \cdot 1 = 2$
$Q(3) = Q(0)Q(2) + Q(1)Q(1) + Q(2)Q(0) = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$
$Q(4) = Q(0)Q(3) + Q(1)Q(2) + Q(2)Q(1) + Q(3)Q(0) = 1 \cdot 5 + 1 \cdot 2 + 2 \cdot 1 + 5 \cdot 1 = 14$
$Q(5) = Q(0)Q(4) + Q(1)Q(3) + Q(2)Q(2) + Q(3)Q(1) + Q(4)Q(0) = 1 \cdot 14 + 1 \cdot 5 + 2 \cdot 2 + 5 \cdot 1 + 14 \cdot 1 = 42$

Step 3: Final Answer:
$Q(5) = 42$.


Example 96: Recurrence for Count of Distinct Patterns

Problem:
Define $P(n) = 2P(n-1)$ with base case $P(0) = 1$. Find $P(5)$.

Answer:

Step 1: Given Data:
$P(0) = 1$

Step 2: Solution:
$P(1) = 2P(0) = 2 \cdot 1 = 2$
$P(2) = 2P(1) = 2 \cdot 2 = 4$
$P(3) = 2P(2) = 2 \cdot 4 = 8$
$P(4) = 2P(3) = 2 \cdot 8 = 16$
$P(5) = 2P(4) = 2 \cdot 16 = 32$

Step 3: Final Answer:
$P(5) = 32$.


Example 97: Recurrence for Count of Unique Game Outcomes

Problem:
Define $O(n) = O(n-1) + O(n-2)$ with base cases $O(1) = 1$, $O(2) = 2$. Find $O(6)$.

Answer:

Step 1: Given Data:
$O(1) = 1$, $O(2) = 2$

Step 2: Solution:
$O(3) = O(2) + O(1) = 2 + 1 = 3$
$O(4) = O(3) + O(2) = 3 + 2 = 5$
$O(5) = O(4) + O(3) = 5 + 3 = 8$
$O(6) = O(5) + O(4) = 8 + 5 = 13$

Step 3: Final Answer:
$O(6) = 13$.


Example 98: Recurrence for Total Ways to Arrange Letters

Problem:
Define $A(n) = A(n-1) + A(n-2)$ with base cases $A(1) = 1$, $A(2) = 2$. Find $A(7)$.

Answer:

Step 1: Given Data:
$A(1) = 1$, $A(2) = 2$

Step 2: Solution:
$A(3) = A(2) + A(1) = 2 + 1 = 3$
$A(4) = A(3) + A(2) = 3 + 2 = 5$
$A(5) = A(4) + A(3) = 5 + 3 = 8$
$A(6) = A(5) + A(4) = 8 + 5 = 13$
$A(7) = A(6) + A(5) = 13 + 8 = 21$

Step 3: Final Answer:
$A(7) = 21$.


Example 99: Recurrence for Count of Unique Paths in a Maze

Problem:
Define $P(n) = P(n-1) + P(n-2)$ with base cases $P(0) = 1$, $P(1) = 1$. Find $P(9)$.

Answer:

Step 1: Given Data:
$P(0) = 1$, $P(1) = 1$

Step 2: Solution:
$P(2) = P(1) + P(0) = 1 + 1 = 2$
$P(3) = P(2) + P(1) = 2 + 1 = 3$
$P(4) = P(3) + P(2) = 3 + 2 = 5$
$P(5) = P(4) + P(3) = 5 + 3 = 8$
$P(6) = P(5) + P(4) = 8 + 5 = 13$
$P(7) = P(6) + P(5) = 13 + 8 = 21$
$P(8) = P(7) + P(6) = 21 + 13 = 34$
$P(9) = P(8) + P(7) = 34 + 21 = 55$

Step 3: Final Answer:
$P(9) = 55$.


Example 100: Recurrence for Total Number of Coins

Problem:
Define $C(n) = C(n-1) + C(n-2)$ with base cases $C(0) = 1$, $C(1) = 1$. Calculate $C(10)$.

Answer:

Step 1: Given Data:
$C(0) = 1$, $C(1) = 1$

Step 2: Solution:
$C(2) = C(1) + C(0) = 1 + 1 = 2$
$C(3) = C(2) + C(1) = 2 + 1 = 3$
$C(4) = C(3) + C(2) = 3 + 2 = 5$
$C(5) = C(4) + C(3) = 5 + 3 = 8$
$C(6) = C(5) + C(4) = 8 + 5 = 13$
$C(7) = C(6) + C(5) = 13 + 8 = 21$
$C(8) = C(7) + C(6) = 21 + 13 = 34$
$C(9) = C(8) + C(7) = 34 + 21 = 55$
$C(10) = C(9) + C(8) = 55 + 34 = 89$

Step 3: Final Answer:
$C(10) = 89$.

adbhutah
adbhutah

adbhutah.com

Articles: 1279