# Thread: Proof a recursive formula with induction

1. ## Proof a recursive formula with induction

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!

2. ## Re: Proof a recursive formula with induction

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.