Hi there.

Soon I have my final exam in Discrete Mathematics, and I'm just working a little bit on proof by induction and refreshing my algebra. There are two exercises that I have some troubles with, and hope that you guys/girls could help me. By the way, sorry if my english is a bit rusty (norwegian).

**Exercise 1:**

For each natural number n, let $\displaystyle t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}$.

Prove that $\displaystyle t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)$

for all $\displaystyle n \in \mathbb{N}$.

**Incomplete answer (Exercise 1):**

I'm going to prove that $\displaystyle t(n + 1) = \binom{2n + 2}{n + 1} = \dfrac{(2n + 2)!}{(n + 1)! * (n + 1)!} \Leftrightarrow \dfrac{4n + 2}{n + 1} * t(n)$.

__Proof:__ $\displaystyle t(n + 1) = \dfrac{(2n + 2)!}{(n + 1)! * (n + 1)!} = \dfrac{4n + 2}{n + 1} * t(n) = \dfrac{4n + 2}{(n + 1)} * \dfrac{(2n)!}{n! * n!} = \dfrac{(4n + 2) * (2n)!}{(n + 1)! * (n + 1)!}$

$\displaystyle = ...$

What now? How can I make $\displaystyle (4n + 2) * (2n)! = (2n + 2)!$ ? Maybe I have done something wrong in the process, or is it my algebra skills?

**Exercise 2:**

Prove by induction that $\displaystyle t(n) \le 4^n$

for all $\displaystyle n \ge 1$. Hint: Use that $\displaystyle 4n + 2 \le 4(n + 1)$.

**Very incomplete answer (Exercise 2):**

__Base step:__$\displaystyle t(1) = 2 \le 4^1 = 4$.

The claim is true for n = 1.

__Inductive step:__

...

Hehe, I'm stuck right here... Hope someone can help me =D

Thanks!