Summary
Highlights
Recurrence reasoning is used to prove a property P(n) for all natural numbers n, or for n greater than or equal to a certain value. It's especially useful when dealing with properties related to natural integers. The process involves three main steps: initialization, heredity, and conclusion.
Initialization: Show that the property is true for the first rank (e.g., n=0, n=1, or n=4, depending on the problem). Heredity: Assume the property is true for a given rank 'n' (P(n)) and show that it must also be true for the next rank (P(n+1)). This is often compared to falling dominoes. Conclusion: State that since the property is true for the initial rank and is hereditary, it is true for all subsequent ranks.
This example uses a sequence defined by u(n+1) = 1/2 * u(n) + 3 with u(0) = -2, to show that u(n) is an increasing sequence. The video walks through initialization for n=0, showing u(1) > u(0), then the heredity step by assuming u(k) <= u(k+1) and proving u(k+1) <= u(k+2).
This example demonstrates how to bound a sequence defined by u(n+1) = sqrt(u(n) + 6) with u(0) = 0. The goal is to prove that 0 <= u(n) < u(n+1) < 3. The initialization for n=0 is shown, followed by the heredity proof involving applying functions (addition and square root) to maintain the inequalities.
This section covers proving formulas for sums using recurrence. The first example proves that the sum of integers from 1 to n (1+2+...+n) is equal to n * (n+1) / 2. The initialization for n=1 and the heredity step, where (n+1) is added to both sides of the assumed equality, are explained.
A more complex sum example, proving that the sum of squares from 1 to n (1^2+2^2+...+n^2) equals n * (n+1) * (2n+1) / 6. The method is similar to the previous sum example, involving meticulous algebraic manipulation to reach the desired (n+1)th term.
This section introduces a different type of recurrence problem: showing that an expression like 7^n + 2 is a multiple of 3. The initialization for n=1 is shown. For heredity, the strategy involves starting with the expression for n+1 (7^(n+1) + 2) and using the recurrence hypothesis (7^n + 2 = 3k) to simplify it and show it's also a multiple of 3.
The final example proves that 2^(3n) - 1 is a multiple of 7 for all natural numbers n. Initialization for n=0 is shown (2^0 - 1 = 0, which is a multiple of 7). The heredity step again involves manipulating the (n+1)th expression (2^(3(n+1)) - 1) and substituting the recurrence hypothesis (2^(3n) - 1 = 7k or 2^(3n) = 7k + 1) to demonstrate it's also a multiple of 7.