How to prove this by mathematical induction?

Question

ok! so i don't have a clue as to how to prove it.

$$\sum\limits_{i=m+1}^n i=((n-m)(n+m+1))/2$$ so the base case is equal to zero because $$\sum\limits_{i=1+1}^1 i=0$$ is this correct? I don't know how to go for inductive step.

Thanks in advance

Answer 1

I suggest you induct on $m$. Fix $n = N$, and then the base case $m=0$ is the familiar arithmetic progression $$\sum_{i=1}^N i = \frac{N(N+1)}{2}.$$ Suppose the result is true for $k = 0, \dots, m$. Then $$ \sum_{i=m+1}^N i = \sum_{i=m}^N i - m = \frac{(N-(m-1))(N+m)}{2} - m = \frac{N^2+N-m^2-m}{2} = \frac{(N-m)(N+m+1)}{2}. $$

Answer 2

You have various options. If I was doing this, I would use double induction as follows : outer induction on $n$ and inner induction on $m$.

First, I would manually show that it holds for $n = 2$, when $m$ is any value in $\{0,1\}.$

Then, I would assume that the conjecture holds for all $n=N$ when $m$ is any value in $\{0,1,\cdots, N-1\}.$

Then, I would show that because it holds for $n = (N)$, it also holds for $n=(N+1)$, when $m$ is any value in $\{0,1,\cdots, N-1, N\}.$

I would do this by holding the value of $n$ as fixed at $(N+1)$, showing that it holds for $m=0$, and then showing that if it holds for any $M$ in $\{0,1,2,\cdots, N-1\}$ with $n = (N+1)$, then it must also hold for $m = (M+1).$

Answer 3

Bearing in mind that your claim - when written out explicitly as a formal predicate - should look as follows: $$R \colon \equiv (\forall m, n)\left(m,n \in \mathbb{N} \wedge m \leqslant n \Rightarrow \sum_{k=m+1}^n k=\frac{(n-m)(n-m+1)}{2}\right),$$ by far the easiest approach is to consider the predicate: $$P(m) \colon \equiv (\forall n) \left(n \in \mathbb{N} \wedge m \leqslant n \Rightarrow \sum_{k=m+1}^n k=\frac{(n-m)(n-m+1)}{2}\right)$$ and realise that $R \Leftrightarrow (\forall m)(m \in \mathbb{N} \Rightarrow P(m))$. Therefore, in order to establish (prove) $R$ it will suffice to fix arbitrary $m \in \mathbb{N}$ and to establish the predicate $P(m)$.

In order to supply a proof for $P(m)$, the most natural choice is to perform induction on the well-ordered set $\{n \in \mathbb{N} \mid n \geqslant m\}$, since this is precisely the domain over which the universal quantifier comprised in $P(m)$ acts.

More explicitly, you would have to perform just one induction where the base case is $n=m$ and the inductive step consists of assuming the summation relation valid for a certain (arbitrary) $n \geqslant m$ in order to deduce it for $n+1$.