# Mathenatucak Induction Problems in discrete math

## Homework Statement

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

## The Attempt at a Solution

Basis Step :
P(1) : [13 + 2(1) ] /3
[1+2] /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

## Homework Statement

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

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

## 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:

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

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:
Mark44
Mentor
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.

Ok, what about the second problem??

Mark44
Mentor
What is the second problem?
GoGoDancer12 said:
Prove that f1 2 + f2 2 +...+ fn 2 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.