Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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).$

share|improve this answer

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.

share|improve this answer

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} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.