4
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – Helana Brock Oct 19 '19 at 22:42
  • $\begingroup$ Is this the step you mean:- $6·3^{k+1}=2·3·3^{k+1} = 2·3^{k+2}$ $\endgroup$ – S. Dolan Oct 19 '19 at 22:47
  • $\begingroup$ 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 $\endgroup$ – Helana Brock Oct 19 '19 at 22:53
  • $\begingroup$ Would you mind editing your answer to be a little more comprehensive on the steps? $\endgroup$ – Helana Brock Oct 19 '19 at 22:54
  • 1
    $\begingroup$ Never-mind. I figured it out $\endgroup$ – Helana Brock Oct 19 '19 at 23:00
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Can you explain a little more? I’m still having trouble even with fixing that $\endgroup$ – Helana Brock Oct 19 '19 at 22:46
  • $\begingroup$ @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. $\endgroup$ – J.G. Oct 20 '19 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.