Question

Prove the explicit formula for the sequence defined recursively by \[a _{1}=1\] and \[a _{k}=2a_{k-1}+6\] is \[a _{n}=7(2^{n-1})-6\] (use mathematical induction)

Answer 1

Here's where i'm at thus far:

Answer 2

let p(k) be: \[a _{k}=7(2^{n-1})-6\]
1. show p(1) is true (that a_1=1):
\[a _{1}=7(2^{(1)-1})-6 = 7(1)-6=1\]

Answer 3

Isn't this the same problem we did last time?

Answer 4

2. show p(k) implies p(k+1)
p(k+1):
\[a _{(k+1)}=7(2^{(k+1)-1})-6=7(2^{k})-6\]

Answer 5

We found the formula yes

Answer 6

I am attempting to prove it with induction now

Answer 7

I see!

Answer 8

@mr math i always forget how to do these, and have to look it up each time (not the proof by induction, finding the formula)
can you link to this answer, i would love to see it

Answer 9

Yea, i can, i asked it :)

Answer 10

http://openstudy.com/#/updates/4ee24839e4b0a50f5c5629c8

Answer 11

thank. i always reinvent the wheel every time. can you complete the inductive step?

Answer 12

Would I just multiply bu (1/2)?

Answer 13

that would give me 7(2^k-1) like i want in p(k)

Answer 14

but would also make 6, 3 which we dont want...

Answer 15

but thats not right, I need to modify p(k) to look like p(k+1), not the other way around

Answer 16

so multiply p(k) by 2.. would be the same issue, 6 as 12

Answer 17

You need to prove that for every integer \(k\ge1\) the explicit formula gives the same value of \(a_k\) as the recursive formula. This is your aim.

Answer 18

You showed that for n=1. Now prove that if it's true for n=k then it's also true for n=k+1.

Answer 19

Right, and I show that by modifying one in such a way that they yield the same result

Answer 20

\[a _{k}=2a_{k-1}+6\] by definition, so your job is to prove that
\[a_{k+1}=7(2^{k})-6\] GIVEN that
\[a_k=7(2^{k-1})-6\]

Answer 21

use first the definition, and then the inductive hypothesis, and it should work out swimmingly

Answer 22

satellite explained it in the best way I could possibly think of.

Answer 23

Yes, so I need to do some algebra on the 2nd equation

Answer 24

Just one step actually.

Answer 25

All I can see to do is multiply by 2, but that changes the 6..

Answer 26

Start from the definition with n=k+1 and use the assumption about n=k to get the explicit formula for n=k+1.

Answer 27

What's \(a_{k+1}\) by definition?

Answer 28

not 7(2^k)-6

Answer 29

\(a_{k+1}=2a_k+6\), right?

Answer 30

Ok yea

Answer 31

But what's \(a_k\) based on your assumption?

Answer 32

I was trying to add something to that expression with a_k-1

Answer 33

Not following.

Answer 34

\[a _{k}=7(k ^{k-1})-6\] base on our assumption

Answer 35

Plug this into the last expression I gave.

Answer 36

comes to \[7(2^{k})\]

Answer 37

Hmm, We have "by definition"
\[a_{k+1}=2a_k+6\]
But we've assumed that \(a_k=7(2^{k-1})-6\), thus
\[a_{k+1}=2(7(2^{k-1})-6)+6=7(2^k)-6.\]

Answer 38

Is this the same as what we had in the explicit formula? YES! PROVED!

Answer 39

You can see it, right?

Answer 40

Apparently you didn't multiply -6 by 2, that's why you got a wrong expression.

Answer 41

Ah, ok

Answer 42

So we dont even need p(k+1) version of the explicit formula?

Answer 43

just a_k+1 and p(k)?

Answer 44

This isnt the same as our explicit formula.

Answer 45

All it is is our p(k+1) formula

Answer 46

Of course it's the same as our explicit formula evaluated at \(n=k+1.\)

Answer 47

Check by plugging n=k+1 in the formula and check for yourself :D

Answer 48

http://imgur.com/Of0yw

Answer 49

What i've written doesn't seem right to me for some reason

Answer 50

It's confusing me too. I think what we wrote above is pretty clear. You just need to read it again. Always remember we want to show that OUR explicit formula gives the same values that the original definition would give.

Answer 51

hmm

Answer 52

Whats confusing is usually with these we show p(k) can be shown to be equivalent to p(k+1) using algebra of some sort, and that is sufficient proof

Answer 53

We started from the definition, used our assumption about a_k to and showed that it's equal to the explicit formula we derived.

Answer 54

Here, it seems we're showing an alternate definition of p(k+1) can be made to look as the other definition of p
p(k+1) using p(k)

Answer 55

We're using the definition you wrote in your question.

Answer 56

yea, the definition is just an alternate version of p(k+1)

Answer 57

What's p(k+1)?

Answer 58

7(2^k)-6?

Answer 59

p(k+1):
\[a _{(k+1)}=7(2^{(k+1)-1})-6\]

Answer 60

yes

Answer 61

That's actually what wanted to show (i.e the statement p(k+1) is true).

Answer 62

and a_k+1 also has the alternate meaning if we use the original definition, (not p(k) or p(k+1)

Answer 63

@satellite: Help me out here, you probably have better explaining abilities :D

Answer 64

ok i will give it a shot but no guarantee (thank you for the compliment though)

Answer 65

our overall goal is to show the explicit formula is true

Answer 66

in the 2nd step of induction our goal is to show that p(k) "implies" p(k+1)

Answer 67

it is my understanding that we can show this implication by showing p(k) can be modified algebraically to look the same as p(k+1)

Answer 68

we have the following definition
\[a _{k}=2a_{k-1}+6\]right? and through some other method (certainly not induction) we found an explicit formula i.e. a formula for
\[a_k\] that did not depend on the recursion
now we wish to show that it works for all k

Answer 69

so we are going to assume that this formula
\[a _{k}=7(k ^{k-1})-6\]works for k, and show that it also works for k + 1

Answer 70

in other words we know that
\[a _{k}=7(k ^{k-1})-6\] and now we want to show that
\[a _{k+1}=7(k ^{k})-6\] as well

Answer 71

wait

Answer 72

are you meaning to write 2^k-1

Answer 73

not k^k-1

Answer 74

yeah that is a typo

Answer 75

k

Answer 76

i follow thus far

Answer 77

we get to assume
\[a _{k}=7(2 ^{k-1})-6\] and we want to show that
\[a _{k+1}=7(2^{k})-6\]

Answer 78

but we have a definition for
\[a_{k+1}\]

Answer 79

it is
\[a_{k+1}=2a_k+6\]

Answer 80

and now we assume (by induction) that our formula works for k, that is we know that
\[a _{k}=7(2 ^{k-1})-6\] so where we see an
\[a_k\]in the above recursion we get to replace it by
\[a _{k}=7(2 ^{k-1})-6\]

Answer 81

ok, so, in induction, it can both ways to prove the implication?

Answer 82

here we go...
\[a_{k+1}=2a_k+6=2\times [7(2^{k-1})-6]+6\]

Answer 83

now we do some algebra on the second part, and if we get
\[a_{k+1}=7(2^{k})-6\] then we win, because that is the formula we are trying to prove

Answer 84

Ok so i guess this is just a different method of induction I am used to

Answer 85

In my previous inductions we had to prove the implication, that is, show p(k) could be modified in some way to resemble p(k+1)

Answer 86

here we are just using both p(k) and p(k+1) to get the explicit formula

Answer 87

i am fairly sure that it may look different but is the same.
btw you notice that induction in a method of proof, but does not help a whit in finding the formula
that is entirely different.

yes, that is exactly what we did. look carefully. i think i see the confusion, because we had to work form the definition to get to the inductive step. in real life the hard part of a proof by induction is reducing to the previous step

Answer 88

so showing p(k+1) can be modified (using p(k) which we know is true) to resemble our explicit formula is proof that p(k+1) is true

Answer 89

is it still appropriate say "show p(k) => p(k+1)" for the 2nd step?

Answer 90

hmm, that pdf isnt working for me

Answer 91

You two here?