# Mathenatucak Induction Problems in discrete math

1. Mar 2, 2010

### GoGoDancer12

1. The problem statement, all variables and given/known data

Prove that 3 divides n3 + 2n whenever n is a positive integer.

2. Relevant equations

3. The attempt at a solution

Basis Step :
P(1) : [13 + 2(1) ] /3
[1+2] /3
[3]/3
1
Since 3/3 =1, P(1) is true

Inductive Step:
[ k3 + 2k ] /3 = [(k +1)3 + 2(k+1) ] /3

[k(k2 + 2k)] /3 = [(k)3 + (3k)2 + 5k +3] /3

1. The problem statement, all variables and given/known data

Prove that f1 2 + f2 2 +...+ fn 2 when n is a positive integer.

2. Relevant equations
The Fibonacci numbers f0, f1, f2..., are defined by the equations f0 = 0, f1 = 1 and fn = fn-1 + fn-2 for n = 2,3,4...

3. The attempt at a solution

Basic Step:
P(1) : f1 2 = f1 * f2

12 = (1)*(1)
1= 1
Since f1 2 = f1 * f2 , P(1) is true.

Inductive Step:
fk 2 = fk * fk+1

fk 2 + fk+1 2
= f1+fk+1 + (fk+1)

Last edited: Mar 2, 2010
2. Mar 2, 2010

### Staff: Mentor

For the first problem, I'm having some trouble understanding what you're doing.
You have established the base case, P(1). IOW, when n = 1, n^3 + 2n = 1 + 2 = 3, so the proposition is true for n = 1.

Assume that the proposition is true when n = k. IOW, assume that k^3 + 2k is divisible by 3. Another way to say this is that k^3 + 2k = 3m for some integer m.

Now, when n = k + 1, you want to show/prove that (k + 1)^3 + 2(k + 1) is divisible by 3. You do NOT want to show that k^3 + 2k = (k + 1)^3 + 2(k + 1), which is essentially what you wrote in your post.

To show that (k + 1)^3 + 2(k + 1) is divisible by 3, expand the two terms. You will need to use the assumption that k^3 + 2k = 3m.

3. Mar 2, 2010

### GoGoDancer12

I'm lost about showing that (k + 1)^3 + 2(k + 1) is divisible by 3. I expanded the right side of the equation [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3. So, do I replace on the left side [k(k^2 + 2k)] /3 with 3m??

Last edited: Mar 2, 2010
4. Mar 2, 2010

### Staff: Mentor

This equation is bogus - [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3 - get rid of it, and also get rid of those /3 things that you have.

Take another look at what I said at the end of my previous post.

5. Mar 3, 2010

### GoGoDancer12

Ok, what about the second problem??

6. Mar 4, 2010

### Staff: Mentor

What is the second problem?
There's nothing there to prove. You have to have a statement of some kind in order to prove it.

Proof by induction, $(n!)^{2} \le (2n)!$. Mar 1, 2017