Another proof by induction.

**jess0517** · July 13th 2010, 07:45 AM

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.

**chiph588@** · July 13th 2010, 07:52 AM

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

**Grandad** · July 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.

Grandad

**jess0517** · July 13th 2010, 09:43 AM

Originally Posted by Grandad

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.

Grandad

Thank u soo much i finally see where i went wrong in my thinking process

**Renji Rodrigo** · July 13th 2010, 12:03 PM

$\sum\limits^n_{k=0} k^2=\frac{n(n+1)(2n+1)}{6}$

summation of integer( k^2) is integer

**Archie Meade** · July 13th 2010, 01:37 PM

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.

Thread: Another proof by induction.

LinkBack

Thread Tools

Display

Another proof by induction.

Similar Math Help Forum Discussions

Proof by Induction

Proof by induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags