Proof with algebra, and proof by induction (problems)

Printable View

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

Incomplete answer (Exercise 1):
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)$ .

Very incomplete answer (Exercise 2):
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!
May 30th 2008, 08:14 PM
mr fantastic

Quote:

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

Quote:

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

Very incomplete answer (Exercise 2):

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.
May 31st 2008, 03:54 AM
kjey

Thank you very much! Very helpfull (Clapping)
June 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 is an integer for .

Answer (Exercise 3):
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:
.

Prove by induction that .

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

Answer (Exercise 3):
Let $t(n) = \frac{(6^n - 1)}{5}$ .
$t(0) = \frac{(6^0 - 1)}{5} = 0$ , the claim is true for $n = 0$ .
I assume that the claim is true for some arbitrary $n = k$ .
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).
$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}$ .
$\frac{6 * 5i + 5}{5}$ is a factor of 5, therefor the claim is proven (I hope...).
Perrrrrfect (Clapping)(Clapping)(Clapping)

Quote:

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 and prove

Now

Algebraic Way:
June 7th 2008, 10:16 AM
kjey

Hmmm... can you explain how $n! - 1 + n * n! = n!(n+1) - 1$ . I'm not a "pro" in algebra (Worried)
June 7th 2008, 10:19 AM
o_O

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