🥇 Inducción matemática para la suma

Inducción matemática para la suma

The proof by mathematical induction (simply known as induction) is a fundamental proof technique that is as important as the direct proof, proof by contraposition, and proof by contradiction. It is usually useful in proving that a statement is true for all the natural numbers mathbb{N}. In this case, we are going to prove summation statements that depend on natural numbers mathbb{N} or the positive integers mathbb{Z}^+.

My other lesson on mathematical induction deals with proving divisibility statements.

Believe me, the steps of proving using mathematical induction can be challenging at first. But when you actually start doing it, you will realize that it is very intuitive and simple. After going through the examples below, you will gain good insights and confidence to tackle much more challenging mathematical induction problems that deal with summations.

Pasos para demostrar por inducción matemática

Show the basis step is true. It means the statement is true for n=1.
Assume true for n=k. This step is called the hipótesis de inducción.
Demuestre que el enunciado es verdadero para n = k + 1. Este paso se llama paso de inducción.

Diagram of Mathematical Induction using Dominoes

Examples of Proving Summation Statements by Mathematical Induction

Ejemplo 1: Use the mathematical to prove that the formula is true for all natural numbers mathbb{N}.

3 + 7 + 11 + … + left( {4n - 1} right) = nleft( {2n + 1} right)

a) Check the basis step n=1 if it is true.

3= nleft( {2n + 1} right)

3 = 1left[ {2left( 1 right) + 1} right]

3 = 1left( 3 right)

3 = 3 ✅

Yes, it is true!

b) Suponga que el enunciado es verdadero para n = k.

color{red}3 + 7 + 11 + … + left( {4k - 1} right) = kleft( {2k + 1} right)

c) Now, we are going to prove that it is true for n=k+1.

3 + 7 + 11 + … + left( {4k - 1} right) + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left[ {2left( {k + 1} right) + 1} right]

Notice that we can greatly simplify the equation using part b).

{color{red}3 + 7 + 11 + … + left( {4k - 1} right)} + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left[ {2left( {k + 1} right) + 1} right]

{color{red}kleft( {2k + 1} right)} + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left[ {2left( {k + 1} right) + 1} right]

The next obvious step is to simplify both sides of the equation. But here’s the thing. We want to simplify the left-hand side (LHS) as much as possible while the right-hand side (RHS) with the least number of steps when simplifying.

There’s nothing wrong if we are heavy on simplifications on both sides as long as we can show that both sides are equal. But it is more elegant that we keep the least amount of simplification on the right side with the most on the left. You will understand this better the more you practice with mathematical induction.

Without touching the left side of the equation, we are going to simplify the right side a bit. Distribute 2 into the binomial inside the parenthesis then add the numbers.

{color{red}kleft( {2k + 1} right)} + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left[ {2left( {k + 1} right) + 1} right]

kleft( {2k + 1} right) + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left( {2k + 2 + 1} right)

kleft( {2k + 1} right) + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left( {2k + 3} right)

Now, it’s time to manipulate the left-hand side so it looks the same as the right-hand side. Apply the Distributive Property twice then combine like terms. Finally, factor out the trinomial. We are done!

kleft( {2k + 1} right) + left[ {4left( {k + 1} right) - 1} right] = left( {k + 1} right)left( {2k + 3} right)

2{k^2} + k + 4k + 3= left( {k + 1} right)left( {2k + 3} right)

2{k^2} + 5k + 3= left( {k + 1} right)left( {2k + 3} right)

left( {k + 1} right)left( {2k + 3} right)= left( {k + 1} right)left( {2k + 3} right) ✔︎

We have shown that if the statement is true for n=k, then it is also true for n=k+1. Therefore, the statement is true for all natural numbers.◾️

Ejemplo 2: Use the mathematical induction to prove that the formula is true for all natural numbers mathbb{N}.

- 1 + 2 + 5 + … + left( {3n - 4} right) = {Large{{n over 2}}}left( {3n - 5} right)

a) Verify the basis step; n=1 is true.

- 1 = {Large{{n over 2}}}left( {3n - 5} right)

- 1 = {Large{{1 over 2}}}left[ {3left( 1 right) - 5} right]

- 1 = {Large{{1 over 2}}}left[ {3 - 5} right]

- 1 = {Large{{1 over 2}}}left( { - 2} right)

- 1 = - 1 ✅

Yes, it is true!

b) Suponga que el enunciado es verdadero para n = k.

color{red} - 1 + 2 + 5 + … + left( {3k - 4} right) = {Large{{k over 2}}}left( {3k - 5} right)

c) Now, we are going to show that it holds true for n=k+1.

- 1 + 2 + 5 + … + left( {3k - 4} right) + left[ {3left( {k + 1} right) - 4} right] = {Large{{{k + 1} over 2}}}left[ {3left( {k + 1} right) - 5} right]

We will use part b) to substitute it into the equation.

{color{red} - 1 + 2 + 5 + … + left( {3k - 4} right)} + left[ {3left( {k + 1} right) - 4} right] = {Large{{{k + 1} over 2}}}left[ {3left( {k + 1} right) - 5} right]

{color{red}{Large{k over 2}}left( {3k - 5} right)} + left[ {3left( {k + 1} right) - 4} right] = {Large{{k + 1} over 2}}left[ {3left( {k + 1} right) - 5} right]

Let’s focus on simplifying the right side of the equation first.

{Large{k over 2}}left( {3k - 5} right) + left[ {3left( {k + 1} right) - 4} right] = {Large{{k + 1} over 2}}left[ {3left( {k + 1} right) - 5} right]

{Large{k over 2}}left( {3k - 5} right) + left[ {3left( {k + 1} right) - 4} right] = {Large{{k + 1} over 2}}left[ {3k + 3 - 5} right]

{Large{k over 2}}left( {3k - 5} right) + left[ {3left( {k + 1} right) - 4} right] = {Large{{k + 1} over 2}}left( {3k - 2} right)

It is time to simplify and manipulate the left-hand side to make it appear the same as the right side of the equation.

We have shown that if the statement is true for n=k, then it is also true for n=k+1. Therefore, the statement is true for all natural numbers.◾️

Ejemplo 3: Prove the equation using the mathematical induction that it is true for all natural numbers mathbb{N}.

large{1 + 2 + {2^2} + … + {2^{n - 1}} = {2^n} - 1 }

a) Inspect the basis step; n=1 is true.

large1 = {2^n} - 1

large 1 = {2^1} - 1

large1 = 2 - 1

large1 = 1 ✅

¡Es verdad!

b) Suponga que el enunciado es verdadero para n = k.

color{red}large{1 + 2 + {2^2} + … + {2^{k - 1}} = {2^k} - 1 }

c) If it is true for n=k, then it must be true for n=k+1.

large1 + 2 + {2^2} + … + {2^{k - 1}} + {2^{left( {k + 1} right) - 1}} = {2^{k + 1}} - 1

Usar parte b) to perform a substitution. This is the use of the assumption.

large {color{red}1 + 2 + {2^2} + … + {2^{k - 1}}} + {2^{left( {k + 1} right) - 1}} = {2^{k + 1}} - 1

large {color{red} 2^{k}-1} + {2^{left( {k + 1} right) - 1}} = {2^{k + 1}} - 1

There is no need to simplify the right-hand side. We will simplify and manipulate the left side of the equation so that it looks like the right side of the equation.

large 2^{k}-1 + {2^{left( {k + 1} right) - 1}} = {2^{k + 1}} - 1

Aquí vamos!

We have shown that if the statement is true for n=k, then it is also true for n=k+1. Therefore, the statement is true for all natural numbers.◾️

Ejemplo 4: Prove the equation using the mathematical induction that it is true for all positive integers mathbb{Z}^+.

4 + 9 + 14 + 19 + … + left( {5n - 1} right) ={Large{ {n over 2}}}left( {5n + 3} right)

a) Show the basis step; n=1 is true.

4 = {Large{{n over 2}}}left( {5n + 3} right)

4 ={ Large{{1 over 2}}}left[ {5left( 1 right) + 3} right]

4 = {Large{{1 over 2}}}left[ {5 + 3} right]

4 ={ Large{{1 over 2}}}left( 8 right)

4 = 4 ✅

¡Sí!

b) Suponga cierto para n = k.

color{red}4 + 9 + 14 + 19 + … + left( {5k - 1} right) = {Large{{k over 2}}}left( {5k + 3} right)

c) If it is true for n=k, then n=k+1 must also be true.

4 + 9 + 14 + 19 + … + left( {5k - 1} right) + left[ {5left( {k + 1} right) - 1} right] = {Large{{{k + 1} over 2}}}left[ {5left( {k + 1} right) + 3} right]

Perform a substitution using the information in part b). The seemingly complicated equation is going to be further simplified.

{color{red}4 + 9 + 14 + 19 + … + left( {5k - 1} right)} + left[ {5left( {k + 1} right) - 1} right] = {Large{{{k + 1} over 2}}}left[ {5left( {k + 1} right) + 3} right]

{color{red}{Large{{k over 2}}}left( {5k + 3} right)} + left[ {5left( {k + 1} right) - 1} right] = {Large{{{k + 1} over 2}}}left[ {5left( {k + 1} right) + 3} right]

Ignore the left side of the equation for now. We are going to clean up the right-hand side of the equation first by simplifying it.

{Large{{k over 2}}}left( {5k + 3} right) + left[ {5left( {k + 1} right) - 1} right] = {Large{{{k + 1} over 2}}}left[ {5left( {k + 1} right) + 3} right]

{Large{{k over 2}}}left( {5k + 3} right) + left[ {5left( {k + 1} right) - 1} right] = {Large{{{k + 1} over 2}}}left( {5k + 5 + 3} right)

{Large{{k over 2}}}left( {5k + 3} right) + left[ {5left( {k + 1} right) - 1} right] = {Large{{{k + 1} over 2}}}left( {5k + 8} right)

Our final step is to algebraically manipulate the left-hand side of the equation so that it becomes equal to the right-hand side.

We have shown that if the statement is true for n=k, then it is also true for n=k+1. Therefore, the statement is true for all positive integers.◾️

Ejemplo 5: Use the mathematical induction to prove that the formula is true for all positive integers mathbb{Z}^+.

Large{1 over {1 cdot 2}} + {1 over {2 cdot 3}} + {1 over {3 cdot 4}} + … + {1 over {nleft( {n + 1} right)}} = {n over {n + 1}}

a) Show that the basis step is true for n=1.

Large{1 over {1 cdot 2}} = {n over {n + 1}}

Large{1 over 2} = {n over {n + 1}}

Large{1 over 2} = {1 over {1 + 1}}

Large{1 over 2} = {1 over 2} ✅

¡Es verdad!

b) Suponga cierto para n = k.

color{red}Large{1 over {1 cdot 2}} + {1 over {2 cdot 3}} + {1 over {3 cdot 4}} + … + {1 over {kleft( {k + 1} right)}} = {k over {k + 1}}

c) Now, we are going to show that it will hold true for n=k+1.

Large{1 over {1 cdot 2}} + {1 over {2 cdot 3}} + {1 over {3 cdot 4}} + … + {1 over {kleft( {k + 1} right)}} + {1 over {left( {k + 1} right)left[ {left( {k + 1} right) + 1} right]}} = {{k + 1} over {left( {k + 1} right) + 1}}

Use the assumption written in part b) to perform a substitution. This will greatly simplify the equation we are working on.

Large{color{red}{1 over {1 cdot 2}} + {1 over {2 cdot 3}} + {1 over {3 cdot 4}} + … + {1 over {kleft( {k + 1} right)}}} + {1 over {left( {k + 1} right)left[ {left( {k + 1} right) + 1} right]}} = {{k + 1} over {left( {k + 1} right) + 1}}

Large{color{red}{k over {k + 1}}} + {1 over {left( {k + 1} right)left[ {left( {k + 1} right) + 1} right]}} = {{k + 1} over {left( {k + 1} right) + 1}}

Without paying attention to the left side of the equation, let’s simplify the right side.

Large{k over {k + 1}} + {1 over {left( {k + 1} right)left[ {left( {k + 1} right) + 1} right]}} = {{k + 1} over {left( {k + 1} right) + 1}}

Large{k over {k + 1}} + {1 over {left( {k + 1} right)left[ {left( {k + 1} right) + 1} right]}} = {{k + 1} over {k + 1 + 1}}

Large{k over {k + 1}} + {1 over {left( {k + 1} right)left[ {left( {k + 1} right) + 1} right]}} = {{k + 1} over {k + 2}}

To finish this off, we will manipulate the left-hand side of the equation such that it equals the right-hand side.

We have shown that if the statement is true for n=k, then it is also true for n=k+1. Therefore, the statement is true for all positive integers.◾️

Ejemplo 6: Use the mathematical induction to prove that the formula is true for all positive integers mathbb{Z}^+.

LARGE{1 over 2} + {1 over 4} + {1 over 8} + … + {1 over {{2^n}}} = {{{2^n} - 1} over {{2^n}}}

a) Check the basis step if n=1 is true.

LARGE{1 over 2} = {{{2^n} - 1} over {{2^n}}}

LARGE{1 over 2} = {{{2^1} - 1} over {{2^1}}}

LARGE{1 over 2} = {{2 - 1} over 2}

LARGE{1 over 2} = {1 over 2} ✅

Yes, it is true!

b) Suponga cierto para n = k.

LARGEcolor{red}{1 over 2} + {1 over 4} + {1 over 8} + … + {1 over {{2^k}}} = {{{2^k} - 1} over {{2^k}}}

c) Prove that it is true for n=k+1.

LARGE{1 over 2} + {1 over 4} + {1 over 8} + … + {1 over {{2^k}}} + {1 over {{2^{k + 1}}}} = {{{2^{k + 1}} - 1} over {{2^{k + 1}}}}

Use the assumption to make a substitution in order to simplify the equation.

LARGE{color{red}{1 over 2} + {1 over 4} + {1 over 8} + … + {1 over {{2^k}}}} + {1 over {{2^{k + 1}}}} = {{{2^{k + 1}} - 1} over {{2^{k + 1}}}}

LARGE{color{red}{{{2^k} - 1} over {{2^k}}}} + {1 over {{2^{k + 1}}}} = {{{2^{k + 1}} - 1} over {{2^{k + 1}}}}

We will keep the right-hand side unchanged because it is simplified enough. We will work on the left-hand side to make it look the same as the one on the right.