Recursion Induction

Question

Let $c_0 =3$ and for n>0, let $c_n = c_{n-1} +n.$ What is the first five terms of the sequence? Prove that $$c_n = \frac{n^2+n+6}{2}$$ Need to prove this by induction. Not a homework but I'm trying to self teach myself but I'm stuck on this recursion.

Answer 1

The claim you are trying to prove is

$$P(n) := \mbox{$c_{n}$ is equal to $ \,\,\frac{n^2 + n +6}{2}$}$$

We first prove $P(0)$. This is easy, since

$$\frac{0^2 + 0 + 6}{2} = 3 = c_{0}$$

Now the inductive step, $P(n) \Longrightarrow P(n+1)$. Assume that

$$c_{n} = \frac{n^2 + n +6}{2}$$

We wish to show that

$$c_{n+1} = \frac{(n+1)^2 + (n+1) + 6}{2}$$

To see this, we calculate

$$c_{n+1} = c_{n} + (n+1) = \frac{n^2 + n + 6}{2} + \frac{2(n+1)}{2} \overbrace{=}^{\mbox{a simple calculation}} \frac{(n+1)^2 + (n+1) + 6}{2}$$

And we are done.

Answer 2

Your base step is simple. For the induction step, suppose that $c_n=\frac{n^2+n+6}2,$ and show that $c_{n+1}=\frac{(n+1)^2+(n+1)+6}2.$ Don't forget that $c_{n+1}=c_n+(n+1).$

Answer 3

I know that you want to prove by induction. But just for the sake of completeness, consider this simple proof:

From $c_n = c_{n-1} + n$, it follows that $$c_n = c_0 + \sum_{k=1}^{n}k$$ The sum evaluates to $\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$ (Triangular Number). So $c_n = c_0 + \frac{n(n+1)}{2}$. With $c_0=3$ you get the desired result: $$ c_n = 3+\frac{n(n+1)}{2} = \frac{n(n+1) + 6}{2} = \frac{n^2 +n + 6}{2} $$