# Thread: Mathematical induction

1. ## Mathematical induction

using the Mathematical induction method to prove this ,

$\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...

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

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

4. ## Re: Mathematical induction

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

$\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\}$

5. ## Re: Mathematical induction

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

$\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...
$\Sigma_{r=1}^{n}n(n+2r)=n^2(2n+1)$
Is easier to prove

6. ## 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?????

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

8. ## Re: Mathematical induction

If n=p then,
$\Sigma_{r=1}^{p}(p+2r)=p(2p+1)$
Then i write like this
$\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,
$\Sigma_{r=1}^{p}p+2\Sigma_{r=1}^{p+1}r=p(2p+1)+2(p +1)$
But what about this >> $\Sigma_{r=1}^{p}p$
please give me a solution????????

9. ## Re: Mathematical induction

substitute summation of p from r=1 to p with the eqn u get in n=p

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

11. ## Re: Mathematical induction

I believe RLBrown identified it in post #5

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

QED indeed!