Skip to content

DA4. Recurrence Relations

Statement

In this assignment, we will explore the fundamental concepts of recurrence relations and their solutions.

Imagine that you are a computer scientist working on developing an algorithm for a new video game. The game involves a character that moves through a maze, and you need to develop an algorithm that can calculate the number of paths the character can take to reach the end of the maze.

Task 1

1: Let’s start by discussing what a recurrence relation is. What are the essential characteristics of a recurrence relation? Provide at least two examples to illustrate your points.

According to (Levin, 2021, p.138), “A recurrence relation is an equation relating a term of sequence to previous terms and an initial conditions”.

So the main characteristics of a recurrence relation are:

  • An initial condition: one or more (a few) terms of the sequence that are checked to belong to the recurrence and proven to be correct.
  • An equation: simplifies the calculation of the recurrence for bigger terms, must be proven correct; then it can be used for any term.
  • Example 1: Fibonacci
    • Formula: f(n) = f(n-1) + f(n-2) for f >= 2.
    • Initial: f(0) = 0; f(1)=1.
  • Example 2: The recurrence of the sequence 1, 3, 5, 7.
    • Initial: f(0) =1
    • Formula: f(n) = 1 + 2n for n >=1 where n is the index of the term in the sequence.

Task 2

2: Next, we will delve into homogeneous and non-homogeneous recurrence relations. What is the difference between these two types of recurrence relations? Provide at least two examples to illustrate the differences between the two.

  • According to (Doerr, 2022, p.161), “An nth order linear reflation is homogeneous if f(k)=0 for all k”, but (Levin, 2021, p.175) defines a homogeneous recurrences as the ones that their formulas do not contain additional constants, but only linear multipliers. While the opposite is true for non-homogeneous recurrences.
  • If we looked back to our examples from the previous task, the fibonacci recurrence is homogeneous, as its formula f(n) = f(n-1) + f(n-2), does not contain addition to constants.
  • While the other option is non-homogenous, as the formula f(n) = 1 + 2n, which is an instance of f(n) = m + 2n, where m is the first term in the sequence (it happened to be 1 in our example).

Task 3

3: Which type of recurrence relation is easier to solve (homogeneous or non-homogeneous) for calculating the number of paths through the maze, and why? Discuss the reasons behind your answer and provide some examples to illustrate your points.

  • Usually, Homogenous recurrences are easier to solve (Doerr, 2022) as there are some standard and common ways that can be applied to all of them; while it is hard to make your way around non-homogenous recurrence.
  • Example, let’s tak two examples for the recurrence of the maze path according to x,y where these are the x and y coordinates of the point where you started counting path.
  • The first recurrence: f(x,y) = xy^m + y^n, and the other one: g(x,y) = 4x^2 + 3y + 4 and the difference between the two is the homogenous f it is easier to take out a common factor by dividing both sides of the equations; while it is harder for the non-homogenous g, as the term 4/commonFactor is harder to deal with.

Task 4

4: What does it mean to solve a recurrence relation, and what is arrived from it? What are the various methods for solving recurrence relations, and when are they used? Provide some examples to illustrate the solution process for calculating the number of paths.

  • According to (Levin, 2021, p.167), solving a recurrence involves “converting its recursive definitions to a closed formula”.
  • Levin spoke about telescoping, or guessing as techniques to solve recurrences.
  • After analyzing the sequence, and the recurrence characteristics and trying out some values we can derive some rules that makes us closer to the correct formula; with every change the new formula must be proved to be correct.

References

  • Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. https://discretemath.org/ads/chapter_7.html. Chapter 8: Recursion and Recurrence Relations.
  • Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0. Chapter 2: Sequences.