# Use proof by mathematical induction to prove explicit formula for recursive sequence is correct

Here is the question I am having trouble with.

Suppose you have the following recursively defined sequence:

P1 = 4
Pk = Pk-1+ 4 · 3k for all integers k ≥ 2

Suppose you have used the method of iteration to find the following explicit formula:

P1 = 4
Pn = 2 · 3n+1 - 14 for all integers n ≥ 1

Use proof by mathematical induction to show this is the correct explicit formula.

Here is what I have so far:

Base case: n = 1, 4 = 2 · 31+1 - 14; 4 = 2 · 9 - 14; 4 = 18 - 14; 4 = 4 ✓

Assume: Pk = 2 · 3k+1 - 14 for all integers k >= 1

Now we must show that Pk+1 = 2 · 3(k+1)+1 - 14

Then we must get Pk+1 = Pk + 4 · 3k to look like what was previously stated. First, let’s substitute in our assumption:

(2 · 3k+1 - 14) + 4 · 3k

I will say that’s as far as I got because I have tried simplifying this multiple ways and I cannot even get it close to what it should look like. I’m starting to think I’ve made a mistake elsewhere. Any help is appreciated, thanks!

## 2 Answers

Try using J.G.'s hint and then you can check your answer with the one below.

$$P_k = 2 · 3^{k+1} - 14$$

Therefore

$$P_{k+1} = (2·3^{k+1} - 14)+4.3^{k+1}$$

Add the $$2·3^{k+1}$$ and $$4·3^{k+1}$$ to get $$6·3^{k+1}$$

Then

$$P_{k+1} = 6·3^{k+1} - 14=2·3^{k+2} - 14$$

and you have the correct result.

• I guess what I don’t understand what’s going on between the second and last step, can you add more context as to what’s going on there? – Helana Brock Oct 19 '19 at 22:42
• Is this the step you mean:- $6·3^{k+1}=2·3·3^{k+1} = 2·3^{k+2}$ – S. Dolan Oct 19 '19 at 22:47
• No, I get that i guess, I just don’t get how you go from the part with the substition to the final answer. I’ve been working on this all day and I just can’t seem to get it – Helana Brock Oct 19 '19 at 22:53
• Would you mind editing your answer to be a little more comprehensive on the steps? – Helana Brock Oct 19 '19 at 22:54
• Never-mind. I figured it out – Helana Brock Oct 19 '19 at 23:00

You should have added $$4\cdot 3^{k+1}$$. It'll work now.

• Can you explain a little more? I’m still having trouble even with fixing that – Helana Brock Oct 19 '19 at 22:46
• @HelanaBrock Judging by your last comment on the accepted answer you came to understand this issue as I slept, but for what it's worth the problem was you'd added $P_k+P_{k-1}$, rather than $P_{k+1}-P_k$, to the value of $P_k$ assumed in the inductive step when you tried to verify $P_{k+1}$ has the value that step needs. – J.G. Oct 20 '19 at 6:43