Help with sequence example  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

Help with sequence example

Postby tonyc1970 on Fri Aug 02, 2013 5:30 pm

Hi Everyone,

I am taking a course in Discrete Mathematics (through distance education and only have access twice a week) and have just started the section on sequences and I need help understanding an example in my study guide.

Here is the example:

Let {s(n)} be a sequence defined recursively as: s(1) = 1, s(2) = 3, and s(n) = 3s(n - 1) - 2s(n - 2) for n >= 3.

We want to show that s(n) = 2n - 1for n >= 1.

P(n) : s(n) = 3s(n - 1) - 2s(n - 2) = 2n - 1 for n >= 1.
Induction hypothesis: s(k) = 3s(k - 1) - 2s(k - 2) = 2k - 1 for k <= n.

We want to prove: P(n + 1) : s(n = 1) = 3s((n + 1) - 1) - 2s((n + 1) - 2) = 3s(n) - 2s( n - 1) = 2(n + 1) - 1.

In the lines above we have 3s and 2s. Are those used in the equations or are they simply used to denote the sequence?

Basic Step:
P(1) : s(1) = 1 = 2 - 1 so P(1) is true.

In the basic step I do not understand where the 2 - 1 come from. I think the 1 in s(1) = 1 comes from the number 1 being assigned to s(1). Is this true?


Inductive Step:
Assume: s(k) = 3s(k - 1) - 2s(k - 2) = 2k - 1 for k <= n.
In particular, we assume the statement to be true for n and n - 1.
Thus,

s(n + 1) = 3s(n) - 2s(n - 1)
= 3(2n - 1) - 2(2n - 1 - 1)
= 3(2n) - 3 - 2(2n - 1) + 2
= (2 + 1)2n - 2n - 5
= 2(2n) + 2n - 2n - 1
= 2n + 1 - 1

I am not sure about the inductive step either.

I realize that I may be asking for a lot, but I really could use the help. I appreciate any help you can provide.

Thanks,

Tony
tonyc1970
 
Posts: 13
Joined: Fri Aug 02, 2013 4:58 pm

Sponsor

Sponsor
 

  TOPIC_SOLVED

Postby stapel_eliz on Fri Aug 02, 2013 8:49 pm

tonyc1970 wrote:
Let {s(n)} be a sequence defined recursively as: s(1) = 1, s(2) = 3, and s(n) = 3s(n - 1) - 2s(n - 2) for n >= 3.

We want to show that s(n) = 2n - 1for n >= 1.

P(n) : s(n) = 3s(n - 1) - 2s(n - 2) = 2n - 1 for n >= 1.
Induction hypothesis: s(k) = 3s(k - 1) - 2s(k - 2) = 2k - 1 for k <= n.

We want to prove: P(n + 1) : s(n = 1) = 3s((n + 1) - 1) - 2s((n + 1) - 2) = 3s(n) - 2s( n - 1) = 2(n + 1) - 1.

In the lines above we have 3s and 2s. Are those used in the equations or are they simply used to denote the sequence?

I'm not sure what you mean by this question...?

tonyc1970 wrote:
Basic Step:
P(1) : s(1) = 1 = 2 - 1 so P(1) is true.

In the basic step I do not understand where the 2 - 1 come from. I think the 1 in s(1) = 1 comes from the number 1 being assigned to s(1). Is this true?

The formula they're wanting to prove is that s(n) = 2n - 1. For n = 1, this is 21 - 1 = 2 - 1 = 1. Also, the recursive formula for the sequence of numbers says that the s(1) is a seed value, with s(1) = 1. So they've shown that s(n) = 2n - 1 for n = 1. That is, they've plugged "1" in for "n" in the (hoped-for) formula "s(1) = 3s(n - 1) - 2s(n - 2) = 2n - 1, unless n = 1 or 2, in which case, use the seed values", and have shown that the formula works.

tonyc1970 wrote:
Inductive Step:
Assume: s(k) = 3s(k - 1) - 2s(k - 2) = 2k - 1 for k <= n.
In particular, we assume the statement to be true for n and n - 1.
Thus,

s(n + 1) = 3s(n) - 2s(n - 1)
= 3(2n - 1) - 2(2n - 1 - 1)
= 3(2n) - 3 - 2(2n - 1) + 2
= (2 + 1)2n - 2n - 5
= 2(2n) + 2n - 2n - 1
= 2n + 1 - 1

I am not sure about the inductive step either.

They've assumed that their formula, P(k) = s(k) = 3s(k - 1) - 2s(k - 2), is true for some (unknown, unnamed, unspecified) value "k", and they've turned now to trying to show that the formula works at the next place; that is, for the number right after "k" (being "k + 1"). So they're trying to prove that, if they plug "k + 1" in for "n", they'll get matching stuff on both sides of the equation.

Note: They SHOULD have used "k + 1", not "n + 1" for this part!! :shock:

We have P(k) = 3s(k - 1) - 2s(k - 2). We're working now with P(k + 1) = s(k + 1). Can we show that we get the expected results? Well, s(k + 1) should, by the formula, equal 3s(k - 1) - 2s(k - 2). We have, by assumption, the (assumed) fact that s(k) = 3s(k - 1) - 2s(k - 2). But notice that this formula requires that we make assumptions about the TWO previous terms, being for k - 1 and for k - 2. This is why they say "In particular, we assume the statement to be true for n and n - 1". They should have said why they're assuming that! :roll:

Anyway, we have s(k) = 3s(k - 1) - 2s(k - 2) = 2k - 1 and, "in particular", also s(k - 1) = 3s(k - 2) - 2s(k - 3) = 2k-1 - 1. We are now working with s(k + 1):

s(k + 1) = 3s(k) - 2s(k - 1) <= [by definition for this sequence]
s(k + 1) = 3(2k - 1) - 2(2k-1 - 1) <= [by assumption for n = k and n = k - 1]
s(k + 1) = 3*2k - 3 - 2*2k-1 + 2 <= [by multiplying out]
s(k + 1) = 3*2k - 2*2k-1 - 1 <= [by rearranging and simplifying]
s(k + 1) = 3*2k - 21*2k-1 - 1 <= [because 2 = 21]
s(k + 1) = 3*2k - 2(k-1)+1 - 1 <= [by exponent rules]
s(k + 1) = 3*2k - 2k - 1 <= [by simplification of the exponent]
s(k + 1) = (3 - 1)*2k - 1 <= [by combining the 3* and the (implicit) 1* and subtracting]
s(k + 1) = 2*2k - 1 <= [simplifying 3 - 1]

And then apply the same "2 = 21" trick and apply the same exponent rule again, and you'll get the desired "s(k + 1) = 2k+1 - 1".

For further examples (and the one you've posted is a hard one!), try here. :wink:
User avatar
stapel_eliz
 
Posts: 1803
Joined: Mon Dec 08, 2008 4:22 pm

Re: Help with sequence example

Postby tonyc1970 on Fri Aug 02, 2013 9:43 pm

Hi stapel_eliz, thanks for the reply. I'll read through your notes and also look at the extra examples you link to.
tonyc1970
 
Posts: 13
Joined: Fri Aug 02, 2013 4:58 pm


Return to Discrete Math