Here's another example of a recursive definition:
This is slightly different from the example in the previous video, in that f(n) depends on two previous values of n: f(n-1) and f(n-2). This means that we need two base cases to get the definition started before we can apply the recursive part of the definition.
In one of the dark alleys around Siebel, a mysterious stranger came up to me and whispered this closed form: \(f(n) = 3^n - 2^n\). Let's prove that it's correct. Specifically, our claim will be that
Claim: for all positive integers n, \(f(n) = 3^n - 2^n\).
Our inductive proof will echo the structure of the recursive definition: two base cases, two applications of the inductive hypothesis inside the inductive step. There are examples where the inductive proof needs to have a slightly different structure (e.g. more base cases). However, an extremely good initial assumption is that the two will be similar.
So, in particular, we need two base cases. These should be for the first two values of n covered by the claim, i.e. 1 and 2.
Proof: by induction on n.Base cases: at n=1, f(n) = f(1) = 1.
Also, \(3^n - 2^n = 3^1 - 2^1 = 1\).At n=2, f(n) = f(2) = 5. Also, \(3^n - 2^n = 3^2 - 2^2 = 9 - 4 = 5\).
In both cases, \(f(n) = 3^n - 2^n\).
Here's our inductive hypothesis. Notice that the range of values for the inductive hypothesis starts at the first base case. I'm going to run the range of values up to k-1 (not k) for variety.
Inductive hypothesis: \(f(n) = 3^n - 2^n\) for \(n=1,2,\ldots, k-1\).
Now, set up the goal at the end of the inductive step. Since I ran the inductive hypothesis up to n=k-1, our goal will be the claim at n=k.
Rest of inductive step:
....
So \(f(k) = 3^{k} - 2^{k}\).
As in our previous recursive definition proof, we'll start by using the recursive definition to divide our big object f(k) into smaller objects (f applied to smaller input values).
Rest of inductive step:\(f(k) = 5f(k-1) - 6f(k-2) \) (by the definition of f)
....
So \(f(k) = 3^{k} - 2^{k}\).
Then apply the inductive hypothesis to BOTH of the smaller values of f:
Rest of inductive step:\(f(k) = 5f(k-1) - 6f(k-2) \) (by the definition of f)
\( = 5(3^{k-1} - 2^{k-1}) - 6(3^{k-2} - 2^{k-2})\) (by the inductive hypothesis)
....
So \(f(k) = 3^{k} - 2^{k}\).
Now collect the terms with similar exponential terms:
Rest of inductive step:\(f(k) = 5f(k-1) - 6f(k-2) \) (by the definition of f)
\( = 5(3^{k-1} - 2^{k-1}) - 6(3^{k-2} - 2^{k-2})\) (by the inductive hypothesis)
\( = (5\cdot 3^{k-1} - 6\cdot 3^{k-2}) - (5\cdot 2^{k-1} - 6\cdot 2^{k-2})\)
....
So \(f(k) = 3^{k} - 2^{k}\).
Now we're going to steal a factor of 2 or 3 from the 6's:
Rest of inductive step:\(f(k) = 5f(k-1) - 6f(k-2) \) (by the definition of f)
\( = 5(3^{k-1} - 2^{k-1}) - 6(3^{k-2} - 2^{k-2})\) (by the inductive hypothesis)
\( = (5\cdot 3^{k-1} - 6\cdot 3^{k-2}) - (5\cdot 2^{k-1} - 6\cdot 2^{k-2})\)
\( = (5\cdot 3^{k-1} - 2\cdot 3^{k-1}) - (5\cdot 2^{k-1} - 3\cdot 2^{k-1})\)
....
So \(f(k) = 3^{k} - 2^{k}\).
And now simplify the algebra to finish the middle of the proof:
Rest of inductive step:\(f(k) = 5f(k-1) - 6f(k-2) \) (by the definition of f)
\( = 5(3^{k-1} - 2^{k-1}) - 6(3^{k-2} - 2^{k-2})\) (by the inductive hypothesis)
\( = (5\cdot 3^{k-1} - 6\cdot 3^{k-2}) - (5\cdot 2^{k-1} - 6\cdot 2^{k-2})\)
\( = (5\cdot 3^{k-1} - 2\cdot 3^{k-1}) - (5\cdot 2^{k-1} - 3\cdot 2^{k-1})\)
\( = 3\cdot 3^{k-1} - 2\cdot 2^{k-1} = 3^k - 2^k\)So \(f(k) = 3^{k} - 2^{k}\), which is what we needed to prove.