1

First of all this is a mathematical induction proof. I faced difficulties just with the step 1 when verifying that $P(1)$ is true. Where $n=1$, the L.H.S is $$\sum_{j=0}^n (j+1)=0+1=1$$

Here I faced trouble when trying to prove the right hand side.

By the way, is my left hand side proof correct? How can I prove the R.H.S.?

Daniel W. Farlow
  • 22,531
Surdz
  • 627
  • Hint: For $n=1$ the LHS is $(0+1)+(1+1)=3$ You have two summands: $j=0$ and $j=1$. – callculus42 May 15 '16 at 23:19
  • You don't "prove the R.H.S.", you calculate and simplify as much as you can the L.H.S. and the R.H.S and prove, in fact observe, that they are equal. – MasB May 15 '16 at 23:26
  • For $n=1$ the RHS is $\frac{(1+1)\cdot (1+2)}{2}=\frac{2\cdot 3}{2}=3$. But there are more steps according the induction. Are you familiar with them ? – callculus42 May 15 '16 at 23:27
  • Note that if you are trying to prove the identity for when $n$ is nonnegative, then this means your base case should be when $n=0$, not $n=1$. Hence, you would have $\sum_{i=0}^0(i+1)=0+1=1=\frac{(0+1)(0+2)}{2}$, thus confirming the base case. Then you would have the inductive hypothesis and so on. – Daniel W. Farlow May 15 '16 at 23:37
  • @ callculus can you elaborate on the formation of the inductive hypothesis of the above question. – Surdz May 16 '16 at 00:21

2 Answers2

1

So how induction works is that we first need to prove our base case. In this problem the base case is $n=1$. The $n=1$ base case yields $\sum_{j=o}^1 (j+1) = (0+1)+(1+1) = 3 = \frac{(1+1)(1+2)}{2}$. So this proves the base case since the answer to $\sum_{j=o}^1 (j+1)$ is of the form $\frac{(n+1)(n+2)}{2}$.

We now make our assumption (the inductive hypothesis). In my proof I assumed it to be true for $n=(k-1)$ and then proved it to be true for $n=k$. In Daniels proof above he assumed it to be true for $n=k$ and then proved it to be true for $n=(k+1)$. Both ways are fine and in this case neither one is harder than the other.

So, assume the statement is true for $n = (k-1) $ for an integer $k$ which means $\sum_{j=o}^{k-1} (j+1) =\frac{((k-1)+1)((k-1)+2)}{2} = \frac{k(k+1)}{2}$ and we are going to use this to show true for $n = k$ by noting that $\sum_{j=o}^k (j+1) = \sum_{j=o}^{k-1} (j+1) + (k+1) $. What we did here was we wrote the last term in the sum separately and this allows us to use our inductive hypothesis in the following way:

Since we already know that $ \sum_{j=o}^{k-1} (j+1) = \frac{k(k+1)}{2}$ from the inductive hypothesis then $\begin{align} \sum_{j=o}^k (j+1) &= \sum_{j=o}^{k-1} (j+1) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ & =\frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{align}$

And this is what we wanted to show.

alpastor
  • 1,460
1

Here is the main part of the inductive step: \begin{align} \sum_{i=0}^{k+1}(i+1)&= \sum_{i=0}^k(i+1)+(k+2)\tag{by definition}\\[1em] &= \frac{(k+1)(k+2)}{2}+(k+2)\tag{by inductive hyp.}\\[1em] &= \frac{(k+1)(k+2)+2(k+2)}{2}\tag{common denom.}\\[1em] &= \frac{(k+2)(k+1+2)}{2}\tag{factor out $(k+2)$}\\[1em] &= \frac{(k+2)(k+3)}{2}.\tag{simplify} \end{align}

Daniel W. Farlow
  • 22,531
  • what is the latex you use to write down the steps right-justified? That's pretty cool – Siddharth Bhat May 15 '16 at 23:37
  • concerning the inductive hypothesis, why ...+ (k+2) at the end again. – Surdz May 15 '16 at 23:38
  • @SiddharthBhat You can actually see all of the code for yourself by either "fake editing" my post (so the raw text is visible) or you can right-click on the portion of typeset math you are interested in seeing the code for and follow Show Math As -> TeX Commands. Then you can see all of the relevant details. – Daniel W. Farlow May 15 '16 at 23:40
  • 1
    @NemanNasawa Do you know what your end-goal is for the inductive step? You are trying to somehow use the inductive hypothesis to reach the point where you obtain $\frac{(k+2)(k+3)}{2}$, and this is easily done by factoring out $k+2$ as done above. Of course, I am sure there are other ways to obtain "the RHS" but they would likely be more complicated and less efficient. – Daniel W. Farlow May 15 '16 at 23:41
  • @DanielW.Farlow - thanks! Did not know that :) – Siddharth Bhat May 15 '16 at 23:45
  • @SiddharthBhat Sure thing! TeX is the coolest thing ever...someday I will know it better hopefully. On MSE, adding additional vertical space between lines seems to be very effective for readability. It's great. – Daniel W. Farlow May 15 '16 at 23:46
  • @ Daniel W.Farlow, Can you elaborate more on how you factor out k+2 above. – Surdz May 16 '16 at 03:23