# Thread: Proof with algebra, and proof by induction (problems)

1. ## Proof with algebra, and proof by induction (problems)

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
$t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}$.
Prove that
$t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)$
for all $n \in \mathbb{N}$.

I'm going to prove that
$t(n + 1) = \binom{2n + 2}{n + 1} = \dfrac{(2n + 2)!}{(n + 1)! * (n + 1)!} \Leftrightarrow \dfrac{4n + 2}{n + 1} * t(n)$.
Proof:
$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)!}$
$= ...$
What now? How can I make $(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
$t(n) \le 4^n$
for all $n \ge 1$. Hint: Use that $4n + 2 \le 4(n + 1)$.

Base step:
$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!

2. Originally Posted by kjey
[snip]
Exercise 1:
For each natural number n, let
$t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}$.

Prove that
$t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)$
for all $n \in \mathbb{N}$.
[snip]
$t(n+1) = \dfrac{(2[n+1])!}{(n+1)! \, (n+1)!} = \dfrac{(2n+2)!}{(n+1) n! \, (n+1) n!} = \dfrac{(2n+2) (2n + 1) (2n)!}{(n+1) n! \, (n+1) n!}$

$= \dfrac{(2n+2)(2n+1)}{(n+1)^2} ~ \dfrac{(2n)!}{n! \, n!} = \dfrac{2(n+1)(2n+1)}{(n+1)^2} \, t(n) = \dfrac{2(2n+1)}{n+1} \, t(n)$.

3. Originally Posted by kjey
[snip]Exercise 2:
Prove by induction that
$t(n) \le 4^n$
for all $n \ge 1$. Hint: Use that $4n + 2 \le 4(n + 1)$.

Base step:
$t(1) = 2 \le 4^1 = 4$.
The claim is true for n = 1.
[snip]
Step 2: Assume true for n = k > 1, that is, $t(k) \leq 4^k$ (inductive hypothesis).

Step 3: Show that it follows from step 2 that it's true for n = k + 1.

It follows from Exercise 1 that $t(k+1) = \dfrac{4k + 2}{k+1}\, t(k)$. Therefore, from the inductive hypothesis:

$t(k+1) \leq \dfrac{4k + 2}{k+1}\, 4^k \leq \dfrac{4k + {\color{red}4}}{k+1}\, 4^k = \dfrac{4(k + 1)}{k+1}\, 4^k = 4^{k+1}$.

Therefore etc. etc.

4. Thank you very much! Very helpfull

5. One (two?) more problem(s):

Exercise 3:
I think I have solved this one, but I want a confirmation that it is correct.

Prove that $\frac{(6^n - 1)}{5}$ is an integer for $n \ge 0$.

1. Let $t(n) = \frac{(6^n - 1)}{5}$.
2. $t(0) = \frac{(6^0 - 1)}{5} = 0$, the claim is true for $n = 0$.
3. I assume that the claim is true for some arbitrary $n = k$.
4. The formula is true if $(6^k - 1)$ is a factor of 5, hence $(6^k - 1) = 5i$ when $i$ is an integer (this is the inductive hypothesis).
5. $t(k + 1) = \frac{(6^{k+1} - 1)}{5} = \frac{6 * 6^k - 1}{5} = \frac{6 * (6^k -1) + 5}{5} = \frac{6 * 5i + 5}{5}$.
6. $6 * 5i + 5$ is a factor of 5, therefor the claim is proven (I hope...).
Exercise 4:
$t(1) = 1, t(n) = t(n - 1) + n * n!$.

Prove by induction that $t(n) = (n + 1)! - 1$.

I understand how I can prove this, but I dont see how I can use algebra-manipulation to do this. Hope someone can help me!

6. Originally Posted by kjey
One (two?) more problem(s):

Exercise 3:
I think I have solved this one, but I want a confirmation that it is correct.

Prove that $\frac{(6^n - 1)}{5}$ is an integer for $n \ge 0$.

1. Let $t(n) = \frac{(6^n - 1)}{5}$.
2. $t(0) = \frac{(6^0 - 1)}{5} = 0$, the claim is true for $n = 0$.
3. I assume that the claim is true for some arbitrary $n = k$.
4. The formula is true if $(6^k - 1)$ is a factor of 5, hence $(6^k - 1) = 5i$ when $i$ is an integer (this is the inductive hypothesis).
5. $t(k + 1) = \frac{(6^{k+1} - 1)}{5} = \frac{6 * 6^k - 1}{5} = \frac{6 * (6^k -1) + 5}{5} = \frac{6 * 5i + 5}{5}$.
6. $\frac{6 * 5i + 5}{5}$ is a factor of 5, therefor the claim is proven (I hope...).
Perrrrrfect

Exercise 4:
$t(1) = 1, t(n) = t(n - 1) + n * n!$.

Prove by induction that $t(n) = (n + 1)! - 1$.

I understand how I can prove this, but I dont see how I can use algebra-manipulation to do this. Hope someone can help me!

Induction way:

t(2) is evident. Assume the result for n - 1 and prove for n.

That is assume $t(n-1) = n! - 1$ and prove $t(n) = (n + 1)! - 1$

Now $t(n) = t(n - 1) + n . n! = n! - 1 + n . n! = n!(n+1) - 1 = (n+1)! - 1$

Algebraic Way:

$t(n) = t(n - 1) + n . n! =t(n - 1) + (n+1)! - n!$

$\Rightarrow t(m) - t(m - 1) = (m+1)! - m! \Rightarrow \sum_{m=2}^{m=n}t(m) - t(m - 1) = \sum_{m=2}^{m=n} (m+1)! - m!$

$\Rightarrow t(n) - t(1) = (n+1)! - 2! \Rightarrow t(n) = (n+1)! - 2 + t(1) \Rightarrow t(n) = (n + 1)! - 1$

7. Hmmm... can you explain how $n! - 1 + n * n! = n!(n+1) - 1$. I'm not a "pro" in algebra

8. $n! - 1 + n \cdot n! \: \: = \: \: n! + n\cdot n! - 1 \: \: = \: \: n!(1+ n) - 1 \: \: = \: \: n!(n+1) - 1$

Basically factored out n! from (n! + nn!).

9. Thanks I should have understand it in the first place

Anyway, my teacher (professor) said that one task at the exam could be to prove a linear recurrence equation (at(n) + bt(n - 1) + ct(n - 2) = 0). There are no examples in the book, and he have never showed it to us. Could some one give me a task that I can solve? I know how to solve the equation, but I have never proved it...