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

• May 30th 2008, 04:04 PM
kjey
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
$\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}$.

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)$.

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!
• May 30th 2008, 08:14 PM
mr fantastic
Quote:

Originally Posted by kjey
[snip]
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}$.
[snip]

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

$\displaystyle = \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)$.
• May 30th 2008, 08:26 PM
mr fantastic
Quote:

Originally Posted by kjey
[snip]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)$.

Base step:
$\displaystyle 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, $\displaystyle 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 $\displaystyle t(k+1) = \dfrac{4k + 2}{k+1}\, t(k)$. Therefore, from the inductive hypothesis:

$\displaystyle 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.
• May 31st 2008, 03:54 AM
kjey
Thank you very much! Very helpfull (Clapping)
• Jun 7th 2008, 08:45 AM
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 $\displaystyle \frac{(6^n - 1)}{5}$ is an integer for $\displaystyle n \ge 0$.

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

Prove by induction that $\displaystyle 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!
• Jun 7th 2008, 08:58 AM
Isomorphism
Quote:

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 $\displaystyle \frac{(6^n - 1)}{5}$ is an integer for $\displaystyle n \ge 0$.

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

Perrrrrfect (Clapping)(Clapping)(Clapping)

Quote:

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

Prove by induction that $\displaystyle 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 $\displaystyle t(n-1) = n! - 1$ and prove $\displaystyle t(n) = (n + 1)! - 1$

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

Algebraic Way:

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

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

$\displaystyle \Rightarrow t(n) - t(1) = (n+1)! - 2! \Rightarrow t(n) = (n+1)! - 2 + t(1) \Rightarrow t(n) = (n + 1)! - 1$
• Jun 7th 2008, 10:16 AM
kjey
Hmmm... can you explain how $\displaystyle n! - 1 + n * n! = n!(n+1) - 1$. I'm not a "pro" in algebra (Worried)
• Jun 7th 2008, 10:19 AM
o_O
$\displaystyle 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!).
• Jun 8th 2008, 01:20 PM
kjey
Thanks (Clapping) I should have understand it in the first place (Headbang)

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...