## Help with sequence example

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
tonyc1970
Posts: 13
Joined: Fri Aug 02, 2013 4:58 pm
Contact:

### Help with sequence example

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

stapel_eliz
Posts: 1628
Joined: Mon Dec 08, 2008 4:22 pm
Contact:
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...?
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.
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!!

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!

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.

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