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

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}\)


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:

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:

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.

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: