Mathematical induction

• Apr 13th 2014, 08:23 AM
srirahulan
Mathematical induction
using the Mathematical induction method to prove this ,

$\displaystyle \Sigma_{r=1}^{n}n(n+2r)=n(2n+1)$ In this problem can i start with substitute n=1 and continue or substitute r=1 and continue...
• Apr 13th 2014, 09:29 AM
prasum
Re: Mathematical induction
substitute n=1 and do summation for r and then it is true for n so prove it for n+1 using n
• Apr 13th 2014, 01:38 PM
HallsofIvy
Re: Mathematical induction
There is no "r" to substitute 1 for! The "r" is a "dummy"- it takes on values of 1 up to n so it would not make sense to "substitute 1" for it.
• Apr 13th 2014, 02:25 PM
romsek
Re: Mathematical induction
Quote:

Originally Posted by srirahulan
using the Mathematical induction method to prove this ,

$\displaystyle \Sigma_{r=1}^{n}n(n+2r)=n(2n+1)$ In this problem can i start with substitute n=1 and continue or substitute r=1 and continue...

as with most induction problems show that $P(1)=True$ and that $P(n) \Rightarrow P(n+1)$

$P(1) = \left\{\displaystyle{\sum_{r=1}^1}1(1+2r)=1(2\cdot 1 + 1)\right\}=\left\{3=3\right\}=True$

I leave it to you to show that $P(n) \Rightarrow P(n+1)$ i.e. that

$\left\{\displaystyle{\sum_{r=1}^n}n(n+2r)=n(2n+1) \right\} \Rightarrow \left\{\displaystyle{\sum_{r=1}^{n+1}}(n+1)((n+1)+ 2r)=(n+1)(2(n+1)+1)\right\}$
• Apr 13th 2014, 02:28 PM
RLBrown
Re: Mathematical induction
Quote:

Originally Posted by srirahulan
using the Mathematical induction method to prove this ,

$\displaystyle \Sigma_{r=1}^{n}n(n+2r)=n(2n+1)$ In this problem can i start with substitute n=1 and continue or substitute r=1 and continue...

$\displaystyle \Sigma_{r=1}^{n}n(n+2r)=n^2(2n+1)$
Is easier to prove
• Apr 13th 2014, 06:39 PM
srirahulan
Re: Mathematical induction
when i show n=p is true then what do i add both side L.H.S and R.H.S to shoe n=p+1 is true?????
• Apr 13th 2014, 09:09 PM
prasum
Re: Mathematical induction
hint:for n=p+1 in summation break it into summation for p and then for 1 term and then use substitution for 2rn term from p(n)
• Apr 14th 2014, 03:43 AM
srirahulan
Re: Mathematical induction
If n=p then,
$\displaystyle \Sigma_{r=1}^{p}(p+2r)=p(2p+1)$
Then i write like this
$\displaystyle \Sigma_{r=1}^{p}P+2\Sigma_{r=1}^{p}r=p(2p+1)$
Then add 2(p+1) both side then i comes like this,
$\displaystyle \Sigma_{r=1}^{p}p+2\Sigma_{r=1}^{p+1}r=p(2p+1)+2(p +1)$
But what about this >>$\displaystyle \Sigma_{r=1}^{p}p$
• Apr 14th 2014, 07:29 AM
prasum
Re: Mathematical induction
substitute summation of p from r=1 to p with the eqn u get in n=p
• Apr 14th 2014, 08:01 AM
JeffM
Re: Mathematical induction
$\displaystyle \sum_{r = 1}^n\{n(n + 2r)\} = n\left\{\sum_{r = 1}^n(n + 2r)\right\} = n\left\{\left(\sum_{r=1}^nn\right) + 2\left(\sum_{r=1}^nr\right)\right\} = n\left(n^2 + 2 * \dfrac{n(n + 1)}{2}\right) =$

$n\left(n^2 + 2 * \dfrac{n^2 + n}{2}\right) = n(n^2 + n^2 + n) = n(2n^2 + n) = n^2(2n + 1) \ne n(2n + 1)\ unless\ n = 0\ or\ n = 1.$

$\displaystyle n = 2 \implies \sum_{r = 1}^2\{2(2 + 2r)\} = 2(2 + 2 * 1) + 2(2 + 2 * 2) = 2 * 4 + 2 * 6 = 8 + 12 = 20 =$

$4 * 5 = 2^2(2 * 2 + 1)\ne 2(2 * 2 + 1).$

$\displaystyle n = 3 \implies \sum_{r = 1}^3\{3(3 + 2r)\} = 3(3 + 2 * 1) + 3(3 + 2 * 2) + 3(3 + 2 * 3) = 3(5 + 7 + 9) = 3 * 21 = 3 * 3 * 7 =$

$3^2(2 * 3 + 1) \ne 3(2 * 3 + 1).$

The student is trying to prove a falsity and so is understandably having trouble. I suggest we ask the student to check what the actual proposition to be proven is.

EDIT: Romsek is correct. RL Brown identified that what was trying to be proved is false several posts back. I am leaving my post up, however, because this student needs it spelled out.
• Apr 14th 2014, 08:02 AM
romsek
Re: Mathematical induction
I believe RLBrown identified it in post #5
• Apr 14th 2014, 09:47 AM
JeffM
Re: Mathematical induction
I think this student is struggling enough to warrant an answer.

The intuition behind proofs by induction is this: if something is true for the next integer if it is true for this integer and if that something is also true for 1, then it is true for 2, which means it is true for 3, which means it is true for 4, and so on forever and ever and ever. Got the intuition?

Now for the proof that a proposition P(n) is true for every positive integer n, the structure of a proof by weak mathematical induction is this:

Step 1: Prove P(1) is true.

Now this means that there is at least one positive integer for which P is true. Choose an arbitrary one of such positive integers (call it k). So P(k) is true. This is frequently called the "induction hypothesis." It is not a mere assumption. You have proved in step 1 that such numbers exist.

Step 2: Prove P(k + 1) is true given that P(1) and P(k) are true and k is a positive integer.

Let's do this for your problem.

$\displaystyle Prove\ by\ induction\ that\ n\ is\ any\ positive\ integer \implies \left\{\sum_{r = 1}^nn(n + 2r)\right\} = n^2(2n + 1).$

Now as a practical matter I like to see whether the proposition is true for 2 and 3 before I do the proof so I don't waste time on trying to prove a falsity, but that is NOT part of a formal proof. OK Formal proof

Step 1

$\displaystyle n = 1 \implies \left\{\sum_{r = 1}^nn(n + 2r)\right\} = 1(1 + 2 * 1) = 1(2 * 1 + 1) = 1^2(2 * 1 + 1) = n^2(2n + 1).$

Thus there exists a positive integer k such that $\displaystyle \left\{\sum_{r = 1}^kk(k + 2r)\right\} = k^2(2k + 1) = 2k^3 + k^2.$

Step 2

$\displaystyle \left\{\sum_{r = 1}^{k+1}(k + 1)(\{k + 1\} + 2r)\right\} = \left\{\sum_{r = 1}^k(k + 1)(\{k + 1\} + 2r)\right\} + (k + 1)\{(k + 1) + 2(k + 1)\} =$

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

$\displaystyle \left\{\sum_{r = 1}^kk\{1 + (k + 2r)\right\} + \left\{\sum_{r = 1}^k1(\{k + 1\} + 2r)\right\} + 3k^2 + 6k + 3 =$

$\displaystyle \left\{\sum_{r = 1}^kk\right\} + \left\{\sum_{r = 1}^kk(k + 2r)\right\} + \left\{\sum_{r = 1}^k(k + 1 + 2r)\right\} + 3k^2 + 6k + 3 =$

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

$\displaystyle 2k^3 + 5k^2 + 6k + 3 + \left\{\sum_{r = 1}^k(k + 1 + 2r)\right\}=$

$\displaystyle 2k^3 + 5k^2 + 6k + 3 + \left\{\sum_{r = 1}^kk\right\} + \left\{\sum_{r = 1}^k1\right\} + \left\{\sum_{r = 1}^k2r\right\}=$

$\displaystyle 2k^3 + 5k^2 + 6k + 3 + k^2 + k + 2 * \left\{\sum_{r = 1}^kr\right\}=$

$\displaystyle 2k^3 + 6k^2 + 7k + 3 + 2 * \left\{\sum_{r = 1}^kr\right\}=$

$2k^3 + 6k^2 + 7k + 3 + 2 * \dfrac{k(k + 1)}{2} =$

$2k^3 + 6k^2 + 7k + 3 + k^2 + k=$

$2k^3 + 7k^2 + 8k + 3= (k + 1)(2k^2 + 5k + 3) = (k + 1)(k + 1)(2k + 3) = (k + 1)^2(2k + 2 + 1) =$

$(k + 1)^2\{(2(k + 1) + 1\}.$ QED
• Apr 14th 2014, 10:18 AM
romsek
Re: Mathematical induction
QED indeed!