Induction problem 1

Here is the definition of g, for reference:

g(0) = 2

g(1) = 7

g(k) = g(k-1) + 2g(k-2), for \(k\ge 2\)

What are we proving?

Notice that P(n) is

\(g(n) = 3\cdot2^n + (-1)^{n+1}\)

Your claim is not (for example) one of the following

• g(n) = g(n-1) + 2g(n-2),
• \(3\cdot2^n + (-1)^{n+1}\)

Make sure that you've used the correct claim in your inductive hypothesis and in the goal of your inductive step.

Outline of Solution

Proof: By induction on n.

Base case(s): For n=0, [check claim at n=0]

For n=1, [check claim at n=1]

Inductive hypothesis: Suppose that \(g(n) = 3\cdot2^n + (-1)^{n+1}\) for all integers \(n = 0,1, \ldots, k-1\) (where k is an integer \( \ge 2\)).

Rest of the inductive step:

[A whole bunch of algebra, concluding with our goal:]

Goal of inductive step: \(g(k)= 3\cdot2^{k} + (-1)^{k+1}\)

Self-check

Check your induction hypothesis and goal carefully.

Have you written a strong inductive hypothesis, i.e. true for all previous values up through a bound of k-1 (or k)? Both of the following alternatives are wrong:

• Suppose \(g(k-1) = 3\cdot2^{k-1} + (-1)^{k}\) [A weak hypothesis. Justifies only one of the two places where you need to use the inductive hypothesis in the middle of the inductive step.]
• Suppose \(g(k-1) = 3\cdot2^{k-1} + (-1)^{k}\) and \(g(k-2) = 3\cdot2^{k-2} + (-1)^{k-1}\) [Technically sufficient but bad style. Works only in specialized situations. Learn to write a proper strong hypothesis.]

Did you quote back the claim in inductive hypothesis? In an advanced class, you could get away with saying "the claim." However, in a beginning class like this, you need to be sure you've correctly identified the claim. Moreover you need to convince the grader that you've correctly identified it.

Your inductive hypothesis must assume that the claim is true for values of n up to some upper bound (k-1 in the above). Don't assume the claim is true for all values of n. That's what you're trying to prove. So this is wrong:

• Suppose that \(g(n) = 3\cdot2^n + (-1)^{n+1}\) for all natural numbers n.

Have you used two different variables (e.g. k and n) in stating the inductive hypothesis? The following is wrong, because it's using n for two different purposes.

• Suppose that \(g(n) = 3\cdot2^n + (-1)^{n+1}\) for all integers \(n = 0,1, \ldots, n-1\) (where n is an integer \( \ge 2\)).

Compare the upper bound value for n in your inductive hypothesis (k-1 in the above) to the value for n used in the goal of your inductive step (k in the above). The variable name should be the same and the value in the goal should be one larger than the bound in the inductive hypothesis. So it's ok to use a bound of n=k and a goal of n=k+1. However, the following are all wrong:

• The inductive hypothesis has a bound of n=k and the goal is \(g(k)= 3\cdot2^{k} + (-1)^{k+1}\).
• The inductive hypothesis has a bound of n=k and the goal is \(g(k-1)= 3\cdot2^{k-1} + (-1)^{k}\).
• The inductive hypothesis has a bound of n=k-1 and the goal is \(g(k+1)= 3\cdot2^{k+1} + (-1)^{k+2}\).
• The inductive hypothesis has a bound of n=k-1 and the goal is \(g(n)= 3\cdot2^{n} + (-1)^{n+1}\).