Mathenatucak Induction Problems in discrete math

[GoGoDancer12]

Homework Statement

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

Homework Equations

The Attempt at a Solution

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

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

[k(k² + 2k)] /3 = [(k)³ + (3k)² + 5k +3] /3

Homework Statement

Prove that f₁ ² + f₂ ² +...+ f_n ² when n is a positive integer.

Homework Equations

The Fibonacci numbers f₀, f₁, f₂..., are defined by the equations f₀ = 0, f₁ = 1 and f_n = f_n-1 + f_n-2 for n = 2,3,4...

The Attempt at a Solution

Basic Step:
P(1) : f₁ ² = f₁ * f₂

1² = (1)*(1)
1= 1
Since f₁ ² = f₁ * f₂ , P(1) is true.

Inductive Step:
f_k ² = f_k * f_k+1

f_k ² + f_k+1 ²
= f₁+f_k+1 + (f_k+1)

 

[Mark44]

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.

 

[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??

 

[Mark44]

I'm lost of 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??

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.

 

[GoGoDancer12]

Ok, what about the second problem??

 

[Mark44]

What is the second problem?

Prove that f₁ ² + f₂ ² +...+ f_n ² when n is a positive integer.

There's nothing there to prove. You have to have a statement of some kind in order to prove it.