Skip to content

JA4. Recursion and Solutions of Recurrence Relations

Question 1

1. Explain the recursive function with simple examples.

  • A recursive function is a function that calls itself during its execution. In mathematical terms, it is a function where the value (or the image) of the current argument is defined in terms of the value (or the image) of its previous argument(s).
  • A recursive function must conclude to a base case, so that it does not call itself indefinitely. The base case is the case where the function does not call itself, instead it returns a simple or fixed value. Some recursive functions may have more than one base case, but at least one base case is required.
  • A recurrence formula, which is that defines the relation between the current argument and the previous argument(s), is also required for a recursive function.
  • A solution for a recurrence relation is a formula that gives us a shortcut to find thee value of the current argument without having to find the value of the previous argument(s) first, that is, a relation between the current argument and some constants.
  • As an example let’s take the following sequence, which defines a relation between the element’s index and the value of the element; this sequence represents the number of visitors (in hundreds) to a shop in a week, 1,2,2,2,2,2,2 and then the sequence 1,2,4,6,8,10,12 which represents the total number of visitors to the shop so far.
  • So to find the total number of visitors to the shop in day 4, f(4), we must first find the total numbers of visitors for each day from 1 to 4, such: f(4) = f(1) + f(2) + f(3) + f(4) = 1 + 2 + 4 + 6 = 13. also for the 7th day, f(7) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 2 + 4 + 6 + 8 + 10 + 12 = 43.
  • But, what if we want to know the total number of visitors to the shop in day 100? That will require a 100 calculations, which is not practical. So we need a formula that gives us the total number of visitors to the shop in day 100 without having to calculate the total number of visitors for each day from 1 to 100 (this is the solution for the recurrence relation).
  • We notice the base case for our example f(1) =1 and the recurrence formula f(n) = f(n-1) + 2 (the current argument is defined in terms of the previous argument).
  • But the solution would be f(n) = 2n -2, that is, finding a relation between the current argument and some constants, which is 2n -2 in our example. so that the f(100) = 2(100) -2 = 198 in our example.

Question 2

Solve the following recurrence relation problem:

2. A company manufactures washing machines by importing internal parts from other countries. In the first month, the company produces one washing machine, and in the second month, it produces two machines. Each month, the company assembles the parts to make n machines in the nth month.

a) Set up a recurrence relation to describe the number of machines produced by the company in the first n months.

\[ \begin{aligned} f(1) &= 1 \\ f(2) &= 2 \\ f(n) &= n : n >= 2 \\ \end{aligned} \]

b) How many washing machines are produced by the company in the first year?

\[ \begin{aligned} f(12) &= f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) + f(8) + f(9) + f(10) + f(11) + f(12) \\ &= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 \\ &= 78 \\ \end{aligned} \]

c) Find an explicit formula for the number of washing machines produced by the company in the first n months. Mention the method used to find the formula and show the steps clearly.

  • We defined a function g(n) that maps the month number to the number of washing machines produced so far, while f(n) maps the month number to the number of washing machines produced in that month.
  • To find the explicit formula for g(n) we are going to substitute some values for n and try to find a relation between g(n) and some constants.
\[ \begin{aligned} g(1) &= f(1) = 1 \\ g(2) &= f(1) + f(2) = 1 + 2 = 3 \\ g(3) &= f(1) + f(2) + f(3) = 1 + 2 + 3 = 6 \\ g(4) &= f(1) + f(2) + f(3) + f(4) = 1 + 2 + 3 + 4 = 10 \\ ... \\ g(n) &= f(1) + f(2) + f(3) + ... + f(n) = 1 + 2 + 3 + ... + n \\ \end{aligned} \]
  • We notice that g(n) is the sum of the first n natural numbers, which is a famous formula:
\[ g(n) = 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2} \]
  • The method used is called Iteration.

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.