1
$\begingroup$

Prove that $$\sum_{i=0}^n 2i=n^2+n$$

I attempted to solve the question by proving the base case $n=0$, and assuming the inductive hypothesis $$\sum_{i=0}^n 2i=n^2+n$$ to be true, so $$\sum_{i=0}^{n+1}2i=\sum_{i=0}^n{2i}+2(n+1)=n^2+n+2(n+1)$$

I am confused as to what I should be getting. In the similarly solved examples, some expressions on the right were reduced to the original inductive hypothesis, while others worked on the right side to produce the left side. I worked on the right and got the following result:

$n^2+n+2n+1=n^2+2n+1+n+1=(n+1)^2+(n+1)$ which looks like the inductive hypothesis on the right side.

I am having issues with similar induction proves that involve the summation/sigma notation; one is an inequality and the other is an algebraic expression with 'i' in the denominator. I am not sure if I should include them or ask separately as they are very similar.

$\endgroup$
2
  • 2
    $\begingroup$ Your proof is essentially correct. However, $$n^2 + n + 2(n + 1) = n^2 + n + 2n + \color{red}{2} = n^2 + 2n + 1 + n + 1 = (n + 1)^2 + (n + 1)$$ $\endgroup$ Commented Mar 12, 2017 at 15:09
  • $\begingroup$ Thanks. I wrote it in a weird way because I was copying my own notes; sorry. $\endgroup$
    – user424801
    Commented Mar 12, 2017 at 15:41

3 Answers 3

2
$\begingroup$

Based on your inductive hypothesis, you just need to confirm that:

$$\left(\sum_{i=0}^n 2i\right)+2n+2 \stackrel{?}{=} (n+1)^2 + (n+1)$$

i.e.

$$(n^2+n)+2n+2 = n^2+3n+2\stackrel{?}{=}\\ (n+1)^2 + (n+1) = n^2+2n+1+n+1=n^2+3n+2$$

They are equal, so that is the solution.

$\endgroup$
2
  • $\begingroup$ Yeah I did reach that by working on the right side. $\endgroup$
    – user424801
    Commented Mar 12, 2017 at 15:42
  • $\begingroup$ @Nasser Then if LHS=RHS as demonstrated, the induction is complete. $\endgroup$
    – Argon
    Commented Mar 12, 2017 at 19:09
0
$\begingroup$

An inductive picture-proof involves adding $(n+1)+n-1$ mini-squares along the perpendicular edges of a $n \times (n+1)$ rectangle to make an $(n+1)\times(n+2)$ rectangle.

$\endgroup$
-1
$\begingroup$

Observe that you can take the two out: then

$$\begin{align} \sum_{i=0}^n 2i&=2\sum_{i=0}^n i \\ &= 2\left(\frac{n}{2}(n+1)\right) \\ &=n(n+1) \\ &=n^2+n, \end{align}$$

since $\sum_{i=0}^n i=\frac{n}{2}(n+1)$ by induction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .