Proof a recursive formula with induction

**infnty** · September 27th 2011, 02:27 PM

Hi all!

I'm new here and I could use some help on a homework question.

Problem
Given the following recursive definition:

$\\ $a_0=1$ \\ $a_1=2$ \\ $a_n=\frac{(a_{n-1})^2}{a_{n-2}}$$

I have to proof, using induction, that

$\\ $a_n=2^n$

My current proof is as follows:

Proof
Base step
The formula is correct for the cases n=0 and n=1 (Can be easily verified).

Induction step
Assume the formula is correct for n, we can fill this in:

$a_n = \frac{(2^{n-1})^2}{2^{n-2}}$

$a_n = \frac{2^{2n-2}}{2^{n-2}}$

$a_n = \frac{2^{n-2} \times 2^n}{2^{n-2}}$

$a_n = 2^n$

However, I think I am missing some important induction steps. I don't see the connection between the base step and the induction step.

Any help is appreciated, thanks in advance!

**emakarov** · September 27th 2011, 02:50 PM

In the induction step, you should fix an arbitrary n >= 2 and assume that the claim holds for n - 1 and n - 2. Then you need to prove it for n. In other words, you prove the following statement where P(n) denotes the claim for n: "For all n >= 2, if P(n - 2) and P(n - 1), then P(n)." Since you proved P(0) and P(1), the induction step gives P(2), then from P(1) and P(2) you get P(3) and so on.

The calculations you did are correct.

Thread: Proof a recursive formula with induction

LinkBack

Thread Tools

Display

Proof a recursive formula with induction

Re: Proof a recursive formula with induction

Similar Math Help Forum Discussions

Recursive Formula

recursive formula

recursive formula

[SOLVED] Recursive sequence induction proof

Recursive induction