I got explicit formula to the sequence correct, but confused on checking

[mr_coffee]

Hello everyone.

I got the hard part of the problem done with help from another forum member,
and i transferred it into a gemeotric sum,
which i will show below but I'm confused on the following
directions that my profressor wrote:

Check your answers to 7, 8 and 11 by verifying that your formula satisfies the initial conditions,
and by checking that it satisfies the recurrence relation by substituting it into the recurrence
relation as in Exercise 8.1.9. Include the check as part of your write-up.
Your answer is incomplete if you turn it in without the check, or if you
turn it in even though it does not pass the check. An incomplete answer to 7, 8 or 11
will not be awarded any points, so don't bother turning one in. Instead, if your answer
does not check out, then fix it.

I checked in the section he was talking about and to my luck, no problem
deals with what he is speaking of...but i do have an example of what he means.

In #8 on the image below, i have boxed the check in which he requires. #11. is where I'm stuck,
i'm not sure what I'm suppose to plug in, following his pattern for #8, it looks like he took
the right hand side of the given equation, and set it equal to the formula i found in replace
of f_{k-1} because there is a +2^k after the formula i found in #8 which was: f_n = 2^{n+1} - 3.Sorry if this is confusing but the directions to these problems are the following:

In eavch of 3-15 a sequence is defined recursively. Use iteration to guess
an explicit formula for the sequence.

and here is my work:

http://suprfile.com/src/1/4ni4e7l/lastscan.jpg Thanks!

 

[mattmns]

Not quite what you want. You want to have each exponent on the right hand side to be to the power k-1 (since you are looking at $p_{k-1}$). Also you want 2 times that, so you need to factor the 2 out. So you should have:
$$2p_{k-1} + 3^k = 2 \left(2^{k-1} + 3^{k-1} + \frac{4\cdot 3^{k-1} - 9\cdot 2^{k-1}}{2} \right) + 3^k$$

If you then do some algebra, it all works out.

 

[mr_coffee]

Thanks matt,

So it looks like, I have to get that right hand side to simplify down to the formula i found which is: P_k = 2^k + 3^k + [4*3^k-9*2^k]/2

By looking at that, do you think that is possible or am I misunderstanding somthing?

Because in #8, that's all he did, was he made the right hand side equal the formula i found.

 

[mattmns]

That is exactly what you want to do, and yes it does work out (keep your goal in mind when doing the algebra).

 

[mr_coffee]

Thanks i'll work on it and let you know how it goes

 

[mr_coffee]

i ended up getting:
3*3^k - (7*2^k)/2

I think I'm approaching this wrong,
its not even close to:
2^k + 3^k + [4*3^k-9*2^k]/2

 

[mattmns]

Hmm, not sure how you got that. Let us start from the beginning:

We have the following:

$$2p_{k-1} + 3^k = 2 \left(2^{k-1} + 3^{k-1} + \frac{4\cdot 3^{k-1} - 9\cdot 2^{k-1}}{2} \right) + 3^k$$
$$=2\cdot 2^{k-1} + 2\cdot 3^{k-1} + 4\cdot 3^{k-1} - 9\cdot 2^{k-1}} + 3^k$$ (Just distributing the 2)
$$=2^k + 2\cdot 3^{k-1} + 4\cdot 3^{k-1} - 9\cdot 2^{k-1}} + 3\cdot 3^{k-1}$$ (exponent properties)
$$=2^k + (2+3)\cdot 3^{k-1} + 4\cdot 3^{k-1} - 9\cdot 2^{k-1}}$$ (factoring)
$$=2^k + 3^{k} + 2\cdot 3^{k-1} + 4\cdot 3^{k-1} - 9\cdot 2^{k-1}}$$(distribute the 2 and 3, exponent properties)
$$=2^k + 3^{k} + 6\cdot 3^{k-1} - 9\cdot 2^{k-1}}$$ (group the 2 and 4 from the 3^(k-1))
$$=2^k + 3^{k} + 2\cdot3\cdot 3^{k-1} - 9\cdot 2^{k-1}}$$ (6 = 2x3)
$$=2^k + 3^{k} + 2\cdot 3^{k} - 9\cdot 2^{k-1}}$$ (exponent properties)
$$=2^k + 3^{k} + \frac{2}{2}\left(2\cdot 3^{k} - 9\cdot 2^{k-1}}\right)$$ (multiply by 1)
$$=2^k + 3^{k} + \frac{4\cdot 3^{k} - 9\cdot 2\cdot 2^{k-1}}{2}$$ (distribute 2 on top)
$$=2^k + 3^{k} + \frac{4\cdot 3^{k} - 9\cdot 2^{k}}{2}$$ (exponent properties)
$$=p_k$$

Maybe I showed a little too much work there, but you should notice that I could have "simplified" things, like 2x9 = 18, but we do not always want to do that (remember that we know what we want our answer to be, so try to get the answer to look like that).Actually, your answer of 3*3^k - (7*2^k)/2 is p_k.

As I said above, you have a goal that you want to reach so try to do the algebra with that goal in mind.

$$3\cdot3^k - \frac{7\cdot 2^k}{2} = 3^k + 2\cdot 3^k - \frac{7\cdot 2^k}{2}$$
$$= 3^k + \frac{4\cdot 3^k - 7\cdot 2^k}{2}$$ multiply by 2/2 and then put as a bigger fraction
$$= 3^k + \frac{4\cdot 3^k - 9\cdot 2^k + 2\cdot 2^k}{2}$$ add "0" subtract 2*2^k then add 2*2^k
$$= 3^k + \frac{4\cdot 3^k - 9\cdot 2^k}{2} + \frac{2\cdot 2^k}{2}$$ split up fraction
$$= 2^k + 3^k + \frac{4\cdot 3^k - 9\cdot 2^k}{2}$$
$$= p_k$$

 

[mr_coffee]

Awesome explanation, thanks so much, nice review too.

 

[matt grime]

All he is asking is that when you guess a solution you do two things.

1. Check that the guess is correct for the base case
2. Check that the guess actually satisfies the recurrence relation

I.e. things you should have done anyway but which the teacher is obviously fed up of students ignoring and so is making you remember to do it by this unsubtle but understandable tactic.

 

[mr_coffee]

I understand his reasonings i just was confused on how he was subbing in the explicit formula into the orginal formula, the section he talks of didn't have an example of this kind but used induction rather than this technique.

 

[mattmns]

You are actually doing induction, just in a slightly different way.

First you are showing that the first case(s) are true (think of base case(s)), and then you are showing that if the formula is true for k-1, then it is also true for k (the inductive step).

 

[mr_coffee]

Oh! that does make sense, never thought of it that way, awesome