What is the correct answer to the blanks to show that P(k+1) is true?

Question

Fill in the blanks in the following proof, which shows that the sequence defined by the recurrence relation

fk	=	fk − 1 + 2k for each integer k ≥ 2
f1	=	1

satisfies the following formula.

f_n = 2^{n + 1} − 3 for every integer n ≥ 1

We must show that P(k + 1) is true. In other words, we must show that f_{k + 1} = 2^k+2−3. Now the left-hand side of P(k + 1) is

f_{k + 1}=f_k + 2^{k + 1} by definition of f₁, f₂, f₃, ...

=f_k-1+2^k+2^k+1 by inductive hypothesis

2*(_____) - 3 = _____ by the laws of algebra, and this is the right-hand side of P(k + 1).

Answer 1

Your use of the inductive hypothesis was wrong.

for f_k, you substitute 2^k+1 - 3)

Then, that line becomes

2^k+1 - 3 + 2^k+1

Then, on the next line, as we have 2^k+1 twice on this line, we get

2*(2^k+1) - 3 = 2^k+2 - 3

Note that you first must show that the expression is true for f₁

Show for n = 1; assume for n = k; prove for n = k+1