Recursion in Mathematics
Recursion is a technique that defines a numerical sequence in terms of its preceding term. This is known as the recursive form.
The recursive form is also called inductive, since recursion is closely tied to the principle of mathematical induction.
Recursively Defined Sequences
A sequence is defined recursively (or inductively) if:
- The first k initial terms of the sequence are specified (the base case).
- A rule is provided that determines all subsequent terms based on those initial k values (the inductive step).
Naturally, the initial value k must be an integer greater than or equal to one:
$$ k \ge 1 $$
If k were zero, there would be no starting value, rendering the formula useless.
A Practical Example
Consider a sequence whose terms represent the sums of natural numbers from 1 to 100:
$$ {a_n} = \sum_{i=1}^{100} = (1) + (1+2) + (1+2+3) + (1+2+3+4) + \dots $$
$$ {a_n} = \sum_{i=1}^{100} = 1 + 3 + 6 + 10 + \dots $$
To find the 100th term of this sequence, a100, one would need to calculate all 99 preceding terms.
That’s quite a daunting calculation to do by hand…
For each term, you’d have to sum all previous numbers:
$$ a_1 = 1 \\ a_2 = 1 + 2 = 3 \\ a_3 = 1 + 2 + 3 = 6 \\ a_4 = 1 + 2 + 3 + 4 = 10 \\ \vdots $$
Fortunately, recursion lets us avoid repeatedly adding the same numbers.
Instead, we can define a formula that relates any natural number n to the previous term an-1:
$$ a_n = a_{n-1} + n $$
Checking this for the first four terms (k = 4), it works perfectly:
$$ a_1 = a_0 + 1 = 0 + 1 = 1 \\ a_2 = a_1 + 2 = 1 + 2 = 3 \\ a_3 = a_2 + 3 = 3 + 3 = 6 \\ a_4 = a_3 + 4 = 6 + 4 = 10 \\ \vdots $$
Thanks to recursion, there’s no need to sum all numbers from 1 up to n−1 each time.
You simply add the current number n to the previous sum an−1.
How Recursion Works
A recursive function calls itself one or more times.
This technique is widely used in computer programming because it significantly reduces the amount of code needed for complex calculations.
In recursion, the original problem is broken down into smaller, simpler subproblems.
Why? Because subproblems are easier to solve and involve less data to process.
However, it’s crucial that these subproblems share the same structural pattern as the original problem.
Example. The sum from 1 to 5 and the sum from 1 to 8 are structurally the same problem. The same holds for sums from 1 to 99, 1 to 1000, and so on.
A recursive algorithm repeatedly applies the function to different input values to solve each subproblem.
It then combines the results of these subproblems to solve the original problem as a whole.
An algorithm of this kind is known as a recursive algorithm.
Note. Recursion can dramatically reduce repetitive calculations. However, it’s not always the most efficient solution. Whenever possible, it’s preferable to find a closed-form formula that computes the result directly in a single step. It’s not always feasible - but it’s certainly worth trying.
Closed-Form Formula
What is a Closed-Form Formula?
A closed-form formula defines a sequence without relying on its previous terms.
It’s not always possible to find one - but when you can, it’s extremely advantageous.
Example
Consider the following recursive sequence:
$$ a_n = a_{n-1} + n $$
The closed-form formula for this sequence is:
$$ a_n = \frac{n(n+1)}{2} $$
How to Derive a Closed-Form Formula
Following the scientific method, you can:
- Observe the first k terms of the sequence.
- Identify a mathematical formula that exactly reproduces those k terms.
- Verify the formula using the principle of mathematical induction on the natural numbers.
If the formula is validated by induction, it holds for all natural numbers - not merely for the first k terms.
Note. Often, it’s not easy to derive a formula just by inspecting the first few terms of a sequence. In such cases, one alternative is to search for the closed-form formula using the method of the characteristic equation of the recursive relation. If a solution exists in the form rn, this method can help uncover it.
A Practical Example
Let’s revisit the sequence representing the sum of the natural numbers from 1 to 100.
Here’s its recursive definition:
$$ a_n = a_{n-1} + n $$
Let’s examine the first k = 5 terms:
$$ a_1 = 1 \\ a_2 = 3 \\ a_3 = 6 \\ a_4 = 10 \\ a_5 = 15 \\ \vdots $$
We then try to find a formula that produces the same results.
Consider, for example, the mathematical expression n(n+1)/2:
$$ a_n = \frac{n(n+1)}{2} $$
This formula seems to work perfectly for the first k = 5 terms:
$$ a_1 = \frac{1(1+1)}{2} = 1 \\ a_2 = \frac{2(2+1)}{2} = 3 \\ a_3 = \frac{3(3+1)}{2} = 6 \\ a_4 = \frac{4(4+1)}{2} = 10 \\ a_5 = \frac{5(5+1)}{2} = 15 $$
However, we can’t simply assume it’s valid for all natural numbers up to 100.
So how can we be sure?
Testing the formula manually all the way to k = 100 would be impractical.
Note. Moreover, proving a formula by checking an infinite number of terms is, of course, impossible.
Fortunately, we can confirm the formula’s validity for all natural numbers by proving it with the principle of mathematical induction.
We start by verifying the base case for k = 1:
$$ a_n = \frac{n(n+1)}{2} $$
$$ a_1 = \frac{1(1+1)}{2} = 1 $$
This matches the result we’d get by computing the sum directly:
$$ {a_1} = \sum_{i=1}^{1} a_i = 1 $$
Thus, the base case holds true.
Next, we need to confirm the inductive step.
Assume the formula is true for the first k terms (the induction hypothesis):
$$ P(k) = \frac{k(k+1)}{2} $$
We must prove it’s also true for the next term, k + 1 (the thesis):
$$ P(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2} $$
where k is any integer less than n = 100.
$$ 1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2} $$
Adding (k + 1) to both sides yields:
$$ 1 + 2 + 3 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) $$
$$ 1 + 2 + 3 + \dots + k + (k+1) = \frac{k(k+1) + 2(k+1)}{2} $$
In the numerator on the right, both terms are multiples of (k+1), so we can rewrite it as:
$$ 1 + 2 + 3 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2} $$
This matches precisely the formula for P(k+1) we aimed to prove:
$$ 1 + 2 + 3 + \dots + k + (k+1) = P(k+1) $$
Note. The formula P(n) is: $$ a_n = \frac{n(n+1)}{2} $$ Therefore, for the subsequent term P(n+1), it becomes: $$ a_{n+1} = \frac{(n+1)((n+1)+1)}{2} = \frac{(n+1)(n+2)}{2} $$ This precisely matches the result obtained through induction. If it holds for term (k+1), it holds for every term thereafter as well.
Thus, the formula satisfies the principle of mathematical induction.
We can therefore confidently use the formula P(k) to calculate the sum of the first 100 natural numbers:
$$ P(100) = \frac{100(100+1)}{2} = \frac{100 \times 101}{2} = \frac{10100}{2} = 5050 $$
Hence, the sum of natural numbers from 1 to 100 is 5050.
Note. Of course, we can apply this closed-form formula to any natural number - not just k = 100. For instance, k = 1000, k = 915, and so forth. Since the formula has been confirmed by induction, it holds for all natural numbers.
And so on.
