# Another proof by induction.

• Jul 13th 2010, 07:45 AM
jess0517
Another proof by induction.
I was looking over this problem and im pretty sure you use induction.. but what would your base case be and when subing (k+1) for n, what is the inital formula we want to achieve? I dont exactly know how to approach this problem.
• Jul 13th 2010, 07:52 AM
chiph588@
Quote:

Originally Posted by jess0517
I was looking over this problem and im pretty sure you use induction.. but what would your base case be and when subing (k+1) for n, what is the inital formula we want to achieve? I dont exactly know how to approach this problem.

Attachment 18183

http://www.mathhelpforum.com/math-he...tml#post534980
• Jul 13th 2010, 09:42 AM
Hello jess0517

We have to prove that $\displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n$ is an integer for all $\displaystyle n \in \mathbb{N}$.

First we factorise:

$\displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n=\tfrac16n(2n^2+3 n+1)$
$\displaystyle =\tfrac16n(n+1)(2n+1)$
So we must prove that $\displaystyle n(n+1)(2n+1)$ is a multiple of 6; in other words, that it is a multiple of 2 and of 3.

First, note that one of $\displaystyle n$ and $\displaystyle (n+1)$ is even. So $\displaystyle n(n+1)(2n+1)$ is even.

Next, note that $\displaystyle n$ is either a multiple of 3, in which case there is nothing left to prove; or it leaves a remainder 1 or 2 when divided by 3.

Case I: $\displaystyle n$ leaves a remainder 1; in which case $\displaystyle n = 3m + 1, m \in \mathbb{N}$. Therefore
$\displaystyle 2n+1 = 6m + 3$
and is therefore a multiple of 3.

Case II: $\displaystyle n$ leaves a remainder 2; in which case $\displaystyle n = 3m +2, m \in \mathbb{N}$. Therefore
$\displaystyle n+1 = 3m + 3$
and is therefore a multiple of 3.

This concludes the proof.

• Jul 13th 2010, 09:43 AM
jess0517
Quote:

Hello jess0517

We have to prove that $\displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n$ is an integer for all $\displaystyle n \in \mathbb{N}$.

First we factorise:

$\displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n=\tfrac16n(2n^2+3 n+1)$
$\displaystyle =\tfrac16n(n+1)(2n+1)$
So we must prove that $\displaystyle n(n+1)(2n+1)$ is a multiple of 6; in other words, that it is a multiple of 2 and of 3.

First, note that one of $\displaystyle n$ and $\displaystyle (n+1)$ is even. So $\displaystyle n(n+1)(2n+1)$ is even.

Next, note that $\displaystyle n$ is either a multiple of 3, in which case there is nothing left to prove; or it leaves a remainder 1 or 2 when divided by 3.

Case I: $\displaystyle n$ leaves a remainder 1; in which case $\displaystyle n = 3m + 1, m \in \mathbb{N}$. Therefore
$\displaystyle 2n+1 = 6m + 3$
and is therefore a multiple of 3.

Case II: $\displaystyle n$ leaves a remainder 2; in which case $\displaystyle n = 3m +2, m \in \mathbb{N}$. Therefore
$\displaystyle n+1 = 3m + 3$
and is therefore a multiple of 3.

This concludes the proof.

Thank u soo much i finally see where i went wrong in my thinking process
• Jul 13th 2010, 12:03 PM
Renji Rodrigo
$\sum\limits^n_{k=0} k^2=\frac{n(n+1)(2n+1)}{6}$

summation of integer( k^2) is integer
• Jul 13th 2010, 01:37 PM
Quote:

Originally Posted by jess0517
I was looking over this problem and im pretty sure you use induction.. but what would your base case be and when subing (k+1) for n, what is the inital formula we want to achieve? I dont exactly know how to approach this problem.

Attachment 18183

P(k)

$\frac{1}{3}k^3+\frac{1}{2}k^2}+\frac{1}{6}k$ is an integer ?

P(k+1)

$\frac{1}{3}(k+1)^3+\frac{1}{2}(k+1)^2+\frac{1}{6}( k+1)$ is also an integer ?

Try to prove that P(k) being true causes P(k+1) to be true.

Proof

$\frac{1}{3}(k+1)^3+\frac{1}{2}(k+1)^2+\frac{1}{6}( k+1)=\frac{1}{3}\left(k^3+3k^2+3k+1\right)+\frac{1 }{2}\left(k^2+2k+1\right)+\frac{1}{6}\left(k+1\rig ht)$

$=\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\ right)+\left(k^2+k+\frac{1}{3}+k+\frac{1}{2}+\frac {1}{6}\right)$

$=\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\ right)+\left(k^2+2k+\frac{2}{6}+\frac{3}{6}+\frac{ 1}{6}\right)$

$=\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\ right)+\left(k^2+2k+1\right)$

$\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\r ight)+\left(k+1)^2$

If k is an integer, so is k+1 and (k+1)(k+1).

Hence, if P(k) is true, it causes P(k+1) to be true.

All that remains is to test the proposition P(k) for the first integer.