Discrete Math, Mathematical Inductions

[DiscreteLearner]

I have a problem where I need to use mathematical inductions, however, the professor did not explain this properly and did not provide examples of it. I was hoping someone could help me with the problem because I do not know where to start.

Using Mathematical induction, for all n>0, prove statement X(n) where X(n) is 1²+3²+5²...+(2n+1)² = (n+1)(2n+1)(2n+3)/3

Thanks for your help, I have had a hard enough time with the class, I just don't have a good resource to refer to for the problem.

 

[Steven G]

I have a problem where I need to use mathematical inductions, however, the professor did not explain this properly and did not provide examples of it. I was hoping someone could help me with the problem because I do not know where to start.

Using Mathematical induction, for all n>0, prove statement X(n) where X(n) is 1²+3²+5²...+(2n+1)² = (n+1)(2n+1)(2n+3)/3

Thanks for your help, I have had a hard enough time with the class, I just don't have a good resource to refer to for the problem.

1st verify that 1²+3²+5²...+(2n+1)² = (n+1)(2n+1)(2n+3)/3 is valid for n=0.

Then write that for n=k that 1²+3²+5²...+(2k+1)² = (k+1)(2k+1)(2k+3)/3.

Then show for n=k+1 that 1²+3²+5²...+(2n+1)² = (n+1)(2n+1)(2n+3)/3

Do as much as you can and we'll help you with the rest.

 

[HallsofIvy]

To prove statment P(n) is true for any positive integer
1) Prove P(1) is true
2) Prove "If P(k) is true then P(k+1) is true".

Here P(n) is "\(\displaystyle 1^2+ 3^2+ 5^2+ \cdot\cdot\cdot+ (2n+1)^2= (n+1)(2n+1)(2n+3)/3\)".

When n=1, 2n+1= 3 so P(1) is "\(\displaystyle 1^2+ 3^2= 1+ 9= 10= 2(3)(5)/3\) so P(1) is true.

Suppose that, for some k, P(k), which is "\(\displaystyle 1^2+ 3^2+ 5^2+ \cdot\cdot\cdot+ (2k+ 1)^2= (k+1)(2k+1)(2k+3)/3\)", is true and use that to prove that P(k+1), which is "\(\displaystyle 1^2+ 3^2+ 5^2+ \cdot\cdot\cdot+ (2(k+1)+ 1)^2= ((k+1)+1)(2(k+1)+1)(2(k+1)+3)/3\)".

Notice that, because the left side is a sum, the left side for P(k+1) is just the left side for P(k) plus \(\displaystyle (2(k+1)+ 1)^2= (2k+ 3)^2\) so the right side is \(\displaystyle (k+1)(2k+ 1)(2k+ 3)/3+ (2k+3)^2\). Show that can be expressed as \(\displaystyle ((k+1)+1)(2(k+1)+1)(2(k+1)+ 3)/3= (k+2)(2k+3)(2k+5)/3\).

 

[JeffM]

Mathematical induction is a way to prove that a proposition about integer n P(n) is true for integer b and every integer > b.

First step: prove P(b) is true. Obviously if you cannot prove it true for any integer, you cannot prove it true for more than one.

Mathematicians then usually describe the next step in a very concise but not initially intuitive way. Here is my way. In the first step, we proved that P(b) is true. So there is AT LEAST ONE integer for which P is true.

Second step: Let k be ANY such integer. Thus, k is an integer greater than or equal to b and P(k) is true. Using some or all of those three facts, prove P(k+1) is true.

Therefore, if b = 1, on step 1, we showed that P(1) is true so, by step 2, P(2) is true, which means by step 2 that P(3) is true, and consequently by step 2 P(4) is true, and so on without end.

[MATH]\text {PROVE by induction for any integer } n \ge 1 \text { that } \sum_{j=1}^n j^3 = \left ( \sum_{j=1}^n j \right )^2.[/MATH]
First, we prove it true if n = 1

[MATH]n = 1 \implies \sum_{j=1}^1j^3 = 1^3 = 1 * 1^2 = 1^2 = \left ( \sum_{j=1}^1 j \right )^2.[/MATH]
Frequently, as here, the first step is trivially easy. But it permits us to say that the set of integers for which the proposition is true is not the empty set.

[MATH]\text {Let } k \text { be any integer such that } k \ge 1 \text { and } \sum_{j=1}^k j^3 = \left ( \sum_{j=1}^k j \right )^2.[/MATH]
Now we need to USE what we know about k to work on what the corresponding expressions are for k + 1.

[MATH]\left ( \sum_{j=1}^{k+1} j \right )^2 = \left \{ (k + 1) + \sum_{j=1}^k j \right \}^2 = (k +1)^2 + 2 * \left \{ (k +1) * \sum_{j=1}^k j \right \} + \left ( \sum_{j=1}^k j \right )^2.[/MATH]
Now I presume you know the theorem that for any positive integer n

[MATH]\sum_{j=1}^n j = \dfrac{n(n+1)}{2}.[/MATH]
If you do not know it, it is a good one to prove by induction. I’ll let you do that one. I am going to use it.

[MATH]\therefore \left ( \sum_{j=1}^{k+1} j \right )^2 = k^2 + 2k + 1 + \dfrac{2(k + 1)k(k+1)}{2} + \left ( \sum_{j=1}^k j \right )^2 \ \implies[/MATH]
[MATH]\left ( \sum_{j=1}^{k+1} j \right )^2 = k^2 + 2k + 1 + k(k^2 + 2k +1) + \left ( \sum_{j=1}^k j \right )^2 \implies[/MATH]
[MATH]\left ( \sum_{j=1}^{k+1} j \right )^2 = k^2 + 2k + 1 + k^3 + 2k^2 + k + \left ( \sum_{j=1}^k j \right )^2 \implies[/MATH]
[MATH]\left ( \sum_{j=1}^{k+1} j \right )^2 = k^3 + 3k^2 + 3k +1 + \left ( \sum_{j=1}^k j \right )^2 \implies [/MATH]
[MATH]\left ( \sum_{j=1}^{k+1} j \right )^2 = (k +1)^3 + \left ( \sum_{j=1}^k j \right )^2.[/MATH]
[MATH]\text {But } \left ( \sum_{j=1}^k j \right )^2 = \sum_{j=1}^k j^3 \implies[/MATH]
[MATH]\left ( \sum_{j=1}^{k+1} j \right )^2 = (k + 1)^3+ \left ( \sum_{j=1}^k j \right \}^2 = (k +1)^2 + \sum_{j=1}^k j^3 = \sum_{j=1}^{k+1} j^3.[/MATH]
There we have our proof.

We must express what we want to show about k + 1 in terms of k, and use what we know about k and integers.

Clearer now?

 

[JeffM]

I have noticed a typo in my last line of math.. It should say [MATH](k + 1)^3[/MATH] rather than [MATH](k + 1)^2[/MATH]. I apologize.

 

[Steven G]

To prove statment P(n) is true for any positive integer
1) Prove P(1) is true
2) Prove "If P(k) is true then P(k+1) is true".

Here P(n) is "\(\displaystyle 1^2+ 3^2+ 5^2+ \cdot\cdot\cdot+ (2n+1)^2= (n+1)(2n+1)(2n+3)/3\)".

When n=1, 2n+1= 3 so P(1) is "\(\displaystyle 1^2+ 3^2= 1+ 9= 10= 2(3)(5)/3\) so P(1) is true.

Suppose that, for some k, P(k), which is "\(\displaystyle 1^2+ 3^2+ 5^2+ \cdot\cdot\cdot+ (2k+ 1)^2= (k+1)(2k+1)(2k+3)/3\)", is true and use that to prove that P(k+1), which is "\(\displaystyle 1^2+ 3^2+ 5^2+ \cdot\cdot\cdot+ (2(k+1)+ 1)^2= ((k+1)+1)(2(k+1)+1)(2(k+1)+3)/3\)".

Notice that, because the left side is a sum, the left side for P(k+1) is just the left side for P(k) plus \(\displaystyle (2(k+1)+ 1)^2= (2k+ 3)^2\) so the right side is \(\displaystyle (k+1)(2k+ 1)(2k+ 3)/3+ (2k+3)^2\). Show that can be expressed as \(\displaystyle ((k+1)+1)(2(k+1)+1)(2(k+1)+ 3)/3= (k+2)(2k+3)(2k+5)/3\).

Sorry but you are supposed to show that P(0) is true!