Hi all!

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

Problem

Given the following recursive definition:

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

I have to proof, using induction, that

$\displaystyle \\ $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:

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

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

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

$\displaystyle $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!