# Mathematical Induction

1. Aug 18, 2005

### Oxymoron

Question

Suppose $a,d \in \mathbb{Z}$ and consider the arithmetic sequence $\{a+kd\}_{k\in\mathbb{N}\cup\{0\}}$. Use the Principle of Mathematical Induction to prove that

$$\sum_{k=0}^n a+kd = \frac{1}{2}(n+1)(2a+nd)$$

Last edited: Aug 18, 2005
2. Aug 18, 2005

### neurocomp2003

[1] try it for the base case(guess its n=1 not n=0 summation starts at 1)
[2] assume it for some n-1 OR n
[3] show that [2] leads to n OR n+1
(depends on if your more comfortable n-1 --> n OR n-->n+1
majority of cases they are the same but sometimes its easier to see one over the other)

I suggest if you want more help that you first show us what you've done first.

3. Aug 18, 2005

### Oxymoron

You're too quick Neurocomp , I was typing my solution.

Solution

Let $P(n)$ be that statement that

$$\sum_{k=0}^n a+kd = \frac{1}{2}(n+1)(2a+nd) \quad \dag$$

1. Show that $P(1)$ is true:

$$P(1) = \sum_{k=0}^1 a+kd = (a+0d)+(a+1d) = 2a + d \quad \ddag$$

For $n=1$ the RHS of $\dag$ equals

$$\frac{1}{2}(1+1)(2a + 1d) = 2a+d = \ddag$$

2. Assume true for $P(n)$.

3. Prove true for $P(n+1)$. That is $P(n+1) = \frac{1}{2}(n+2)(2a+(n+1)d)$:

$$\sum_{k=0}^{n+1} a+kd &=& \sum_{k=0}^n a+kd + \sum_{k=n+1}^{n+1} a+kd$$
$$\quad= \sum_{k=0}^n a+kd + [a + d(n+1)]$$
$$\quad= \frac{1}{2}(n+1)(2a+nd) + a + d(n+1)$$
$$\quad= a(n+1) + a + \frac{1}{2}dn(n+1) + d(n+1)$$
$$\quad= a(n+2) + \frac{1}{2}d(n+1)(n+2)$$
$$\quad= \frac{1}{2}(n+2)(2a + (n+1)d)$$
$$\quad= P(n+1)$$

$$\square$$

Last edited: Aug 18, 2005
4. Aug 18, 2005

### Oxymoron

It may be hard to see what I've done in going from

$$a(n+2) + a + \frac{1}{2}dn(n+1) + d(n+1)$$

to the next line.

All Ive done is group the a and [itex]\frac{1}{2}d(n+1)[/tex]

So

$$\frac{1}{2}dn(n+1) + d(n+1) = \frac{1}{2}\left[dn(n+1) + 2d(n+1)\right]$$
$$= \frac{1}{2}d\left[n(n+1) + 2(n+1)\right]$$
$$= \frac{1}{2}d(n+1)\left[n+2\right]$$