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) = 2^{n} - 1for n >= 1.

P(n) : s(n) = 3s(n - 1) - 2s(n - 2) = 2^{n} - 1 for n >= 1.

Induction hypothesis: s(k) = 3s(k - 1) - 2s(k - 2) = 2^{k} - 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) = 2

^{n} - 1. For n = 1, this is 2

^{1} - 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) = 2

^{n} - 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) = 2

^{n} - 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) = 2^{k} - 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(2^{n} - 1) - 2(2^{n - 1} - 1)

= 3(2^{n}) - 3 - 2(2^{n - 1}) + 2

= (2 + 1)2^{n} - 2^{n} - 5

= 2(2^{n}) + 2^{n} - 2^{n} - 1

= 2^{n + 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) = 2

^{k} - 1 and, "in particular", also s(k - 1) = 3s(k - 2) - 2s(k - 3) = 2

^{k-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(2

^{k} - 1) - 2(2

^{k-1} - 1) <= [by assumption for n = k and n = k - 1]

s(k + 1) = 3*2

^{k} - 3 - 2*2

^{k-1} + 2 <= [by multiplying out]

s(k + 1) = 3*2

^{k} - 2*2

^{k-1} - 1 <= [by rearranging and simplifying]

s(k + 1) = 3*2

^{k} - 2

^{1}*2

^{k-1} - 1 <= [because 2 = 2

^{1}]

s(k + 1) = 3*2

^{k} - 2

^{(k-1)+1} - 1 <= [by exponent rules]

s(k + 1) = 3*2

^{k} - 2

^{k} - 1 <= [by simplification of the exponent]

s(k + 1) = (3 - 1)*2

^{k} - 1 <= [by combining the 3* and the (implicit) 1* and subtracting]

s(k + 1) = 2*2

^{k} - 1 <= [simplifying 3 - 1]

And then apply the same "2 = 2

^{1}" trick and apply the same exponent rule again, and you'll get the desired "s(k + 1) = 2

^{k+1} - 1".

For further examples (and the one you've posted is a hard one!), try

here.