5
$\begingroup$

I have been trying to understand how proof by mathematical induction works, and I am struggling a bit. But, I think I am understanding it and I just want to verify that what I am doing is correct (and if not, why?)

I have attached a screenshot (as a link) of my problem (black ink) and my work (red ink). My main issue is understanding what the final conclusion should be. What I did was check to see if the left and right side of the problem were equal after assuming $k + 1$ is true, and adding the appropriate terms to both sides, and simplifying.

So, in my final steps of the induction phase, my question is, did I reach the right result?

Prove: $1 + 3 + 6 + \cdots + \dfrac{n(n + 1)}{2} = \dfrac{n(n + 1)(n + 2)}{6}$.

Base: $P(1) = 1$.

Induction:

\begin{align*} \underbrace{1 + 3 + 6 + \cdots + \frac{k(k + 1)}{2}}_{\dfrac{k(k + 1)(k + 2)}{6}} + \frac{(k + 1)(k + 2)}{2} & = \frac{(k + 1)(k + 2)(k + 3)}{6}\\ \frac{k(k + 1)(k + 2)}{6} + \frac{(k + 1)(k + 2)}{2} & = \frac{(k + 1)(k + 2)(k + 3)}{6}\\ \frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{6} & = \frac{(k + 1)(k + 2)(k + 3)}{6}\\ \frac{(k + 1)(k + 2)(k + 3)}{6} & = \frac{(k + 1)(k + 2)(k + 3)}{6} \end{align*}

Prove: $5 + 10 + 15 + \cdots + 5n = \dfrac{5n(n + 1)}{2}$

Base: $P(1) = 5$

Induction:
\begin{align*} 5 + 10 + 15 + \cdots + 5k + 5(k + 1) & = \frac{5k(k + 1)}{2} + 5(k + 1)\\ \frac{5k(k + 1)}{2} + 5(k + 1) & = \frac{5k(k + 1)}{2} + 5(k + 1) \end{align*} My problem and my work

$\endgroup$
8
  • 1
    $\begingroup$ Your second proof is incomplete. $\endgroup$ – an4s Jul 26 '20 at 21:32
  • $\begingroup$ Can you elaborate? The two sides are equal, right? I don't understand what my final written out step should look like entirely. $\endgroup$ – Justin Saunders Jul 26 '20 at 21:33
  • $\begingroup$ Welcome to MathSE. Please type your work since images cannot be searched. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Jul 26 '20 at 21:34
  • $\begingroup$ @JustinSaunders You need to show that $5 + 10 + 15 + \cdots + 5n + 5(n + 1) = \dfrac{5(n + 1)(n + 2)}2$. In its current form, your proof doesn't exactly show that. Alternatively (and I am not sure if it is accepted convention), you need to show how $\dfrac{5(n + 1)(n + 2)}2$ can be written as $\dfrac{5n(n + 1)}2 + 5(n + 1)$. $\endgroup$ – an4s Jul 26 '20 at 21:38
  • $\begingroup$ @N.F.Taussig I'm rewriting it now in the right format, thanks for the tip! $\endgroup$ – Justin Saunders Jul 26 '20 at 21:41
2
$\begingroup$

In a proof by mathematical induction, we wish to establish that some property $P(n)$ holds for each positive integer $n$ (or for each integer greater than some fixed integer $n_0$). We must first establish that the base case holds. Once we establish that it holds, we may assume the property holds for some positive integer $k$. We then need to prove that if $P(k)$ holds, then $P(k + 1)$ holds. Then, if our base case is $P(1)$, we obtain the chain of implications $$P(1) \implies P(2) \implies P(3) \implies \cdots$$ and $P(1)$, which establishes that the property holds for every positive integer.

You should not assume $P(k + 1)$ is true. We must prove that $P(1)$ holds and that if $P(k)$ holds, then $P(k + 1)$ holds for each positive integer $k$.

Let's look at the first proposition.

Proof. Let $P(n)$ be the statement that $$1 + 3 + 6 + \cdots + \frac{n(n + 1)}{2} = \frac{n(n + 1)(n + 2)}{6}$$

Let $n = 1$. Then $$\frac{n(n + 1)}{2} = \frac{1(1 + 1)}{2} =\frac{1 \cdot 2}{2} = 1 = \frac{1 \cdot 2 \cdot 3}{6} = \frac{1(1 + 1)(1 + 2)}{6}$$ Hence, $P(1)$ holds.

Since $P(1)$ holds, we may assume $P(k)$ holds for some positive integer $k$. Hence, $$1 + 3 + 6 + \cdots + \frac{k(k + 1)}{2} = \frac{k(k + 1)(k + 2)}{6}$$ This is our induction hypothesis.

Let $n = k + 1$. Then \begin{align*} 1 + 3 + 6 + & \cdots + \frac{k(k + 1)}{2} + \frac{(k + 1)(k + 2)}{2}\\ & = \frac{k(k + 1)(k + 2)}{6} + \frac{(k + 1)(k + 2)}{2} && \text{by the induction hypothesis}\\ & = \frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{6}\\ & = \frac{(k + 1)(k + 2)(k + 3)}{6}\\ & = \frac{(k + 1)[(k + 1) + 1][(k + 1) + 2]}{6} \end{align*} Thus, $P(k) \implies P(k + 1)$ for each positive integer $k$.

Since $P(1)$ holds and $P(k) \implies P(k + 1)$ for each positive integer $k$, $P(n)$ holds for each positive integer $n$.$\blacksquare$

I will leave the second proof to you.

$\endgroup$
5
  • $\begingroup$ Ok, I'm gonna try this and see if it makes sense now, thank you. If it works out I'll mark this as the accepted answer :) $\endgroup$ – Justin Saunders Jul 26 '20 at 22:14
  • $\begingroup$ I still don't seem to understand the second problem. I can't figure out what I'm doing wrong or different than what I'm doing on the first problem. The first one makes perfect sense, but the second one, for some reason, is not clicking with me. $\endgroup$ – Justin Saunders Jul 26 '20 at 22:33
  • $\begingroup$ What is your $P(n)$? $\endgroup$ – N. F. Taussig Jul 26 '20 at 22:35
  • $\begingroup$ $P(n)$ is $5n$ Right? $\endgroup$ – Justin Saunders Jul 26 '20 at 22:39
  • $\begingroup$ I see why you are having trouble. $P(n)$ should be the statement that $$5 + 10 + 15 + \cdots + 5n = \frac{5n(n + 1)}{2}$$ This is what we wish to prove. Start by showing that it holds for $1$. Once you establish that, you may assume that $P(k)$ holds for some positive integer $k$. Then you must show that $P(k) \implies P(k + 1)$ in order to conclude that $P(n)$ holds for each positive integer $n$. $\endgroup$ – N. F. Taussig Jul 26 '20 at 22:42
0
$\begingroup$

Yes.... it is okay but it needs a bit of exposition-- that is an explanation of what you are doing and why you are doing it and why it proves what you want.

I would add after you write the word "Induction:" I would expound words to the effect

Induction step: Supose $P(k)$.

Suppose that for some $k$ that $1+ 3+ 6 + ... +\frac {k(k+1)}2 = \frac {k(k+1)(k+2)}6$. Then we must prove $P(k+1)$ or in other words that $1+3 +.....+\frac {(k+1)(k+2)}2 = \frac {(k+1)(k+2)(k+3)}6$.

Then I'd not that as that is what we are attempt to prove I wouldn't write is an "$= \frac {(k+1)(k+2)(k+3)}6$" every step of the way. It's not clear you are attempting to verify a result and looks as though you are stating a bunch of things without cause.

$\require{cancel}$

$\begin{align*} \underbrace{1 + 3 + 6 + \cdots + \frac{k(k + 1)}{2}}_{\dfrac{k(k + 1)(k + 2)}{6}} + \frac{(k + 1)(k + 2)}{2} =& \color{red}{\cancel{= \frac{(k + 1)(k + 2)(k + 3)}{6}}}\\ \frac{k(k + 1)(k + 2)}{6} + \frac{(k + 1)(k + 2)}{2} =&\color{red}{\cancel{= \frac{(k + 1)(k + 2)(k + 3)}{6}}}\\ \frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{6} =& \color{red}{\cancel{= \frac{(k + 1)(k + 2)(k + 3)}{6}}}\\ \frac{(k + 1)(k + 2)(k + 3)}{6} & \color{red}{\cancel{= \frac{(k + 1)(k + 2)(k + 3)}{6}}} \end{align*}$

And we'd be done.

But words like "And therefore we have shown that $P(k) \implies P(k+1)$, and thus the induction step is valid" wouldn't hurt.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.