So far, all of your observations are correct. Note to self: learn latex

To start, here are a few lemmas you will need, some of which you have already observed, others can be easily verified from the definition.

Def:

Lemma 1: if

Lemma 2:

Lemma 3:

Lemma 4:

By lemma 1, , and therefore

Base case: Let . Then the LHS is .

The RHS is . So LHS=RHS for our base case.

Inductive assumption: Suppose for some

Inductive leap: We want to show that ...

(inductive assumption)

(lemma 3)

(lemma 4)

QED