Thread: Induction on a sequence

Show

and deduce the limit is 2.



Assume p(k) is true for a fixed but arbitrary .

Prove p(k+1) is true.

I am having trouble with this piece and not sure where to start.

First, since a_n refers to both a_{n-1} and a_{n-2}, the induction step must deduce P(n) from P(n-1) and P(n-2). I actually prefer to prove that P(k) and P(k+1) imply P(k+2) for k >= 2. Next, P(3) cannot be proved by the induction step because that would require P(1) and P(2), and we don't have P(1). Therefore, P(3) has to be proved as a part of the base case. After that, P(2) and P(3) would give P(4), P(3) and P(4) would give P(5) and so on.

To prove the inductive step, assume P(k) and P(k+1) are true (write these statements explicitly) and use the definition of a_{k+2} to see if a_{k+2} satisfies P(k+2).

Originally Posted by emakarov

First, since a_n refers to both a_{n-1} and a_{n-2}, the induction step must deduce P(n) from P(n-1) and P(n-2). I actually prefer to prove that P(k) and P(k+1) imply P(k+2) for k >= 2. Next, P(3) cannot be proved by the induction step because that would require P(1) and P(2), and we don't have P(1). Therefore, P(3) has to be proved as a part of the base case. After that, P(2) and P(3) would give P(4), P(3) and P(4) would give P(5) and so on.

To prove the inductive step, assume P(k) and P(k+1) are true (write these statements explicitly) and use the definition of a_{k+2} to see if a_{k+2} satisfies P(k+2).

Which a_n do I use to prove this then?

I don't understand your question. I suggest fixing an arbitrary k >= 2 (or call it n), assuming P(k) and P(k+1) and starting from the given equation for a_{k+2} to try to show that it satisfies P(k+2).

Originally Posted by emakarov

I don't understand your question. I suggest fixing an arbitrary k >= 2 (or call it n), assuming P(k) and P(k+1) and starting from the given equation for a_{k+2} to try to show that it satisfies P(k+2).

I have or do I use

Originally Posted by dwsmith

I have or do I use

The second equality is what you have to prove for n = k + 2. The first equality is given in the definition of the sequence a_n. When working informally, one often starts with the equation one needs to prove and transforms it to a valid equation, but the final proof has to start with known equations and end with the one that has to be proved.

By adding k and k+1, I obtain:





Not sure where to go now though.

The defining equation for the sequence says that not only a_k and a_{k+1} have to be added, but also the sum has to be multiplied by 1/2. Secondly, it is natural to factor out (-1/2)^k. Finally, note that (1/2)^2 = (-1/2)^2.

Thanks for the help.