[Math] Guess explicit formula for sequence and then prove it is correct

discrete mathematicssequences-and-series

just trying to work through the following problem but have come to point where I don't know what to do.

Info: Let $a_0, a_1, a_2, …$ be the sequence defined recursively as $a_0 = 0, a_k = k + a_{k-1}$ for each integer $k\ge 1$.

Question is: Using this information write out the first 6 terms of the sequence, guess the explicit formula and then prove your guess is correct.

So I've done as follows:

First 6 terms: $a_0 = 0, a_1 = 1, a_2 = 3, a_3 = 6, a_4 = 10, a_5 = 15, a_6 = 21$

Explicit formula guess: $ a_n = \frac {n^2 + n}{2}$

Proof:

Using the guessed explicit formula $a_n = \frac {n^2 + n}{2}$ for each integer $n \ge 0$ we see that

$a_0 = \frac {0^2 + 0}{2} = 0$ so we have the correct initial condition.

Let $a_0, a_1, a_2, …$ be the sequence defined as $a_0 = 0$ and $a_k = k + a_{k-1}$ for each integer $k \ge 1$

Then, let P(n) be the predicate $a_n = \frac {n^2 + n}{2}$ for each integer $n \ge 0$

Basis step: $a_0 = 0$ from the recursive definition and $\frac {n^2 + n}{2} = 0$, so P(0) is true.

Inductive Hypothesis: Suppose that P(k) is true for some integer $k \ge 0$.

Then $a_{k+1} = (k + 1) + a_k$

= $(k + 1) + \frac {k^2 + k}{2}$

= $\frac{2(k + 1) + (k^2 + k)}{2}$

= $\frac{2k + 2 + k^2 + k}{2}$

= $\frac{k^2 + 3k + 2}{2}$

= $\frac{k^2 + 3k}{2} + 1$??? I'm not sure what to do after the previous step. Any help would be greatly appreciated.

Best Answer

You are doing fine down to the next to last line. Then write $$a_{k+1}=\frac {(k+1)(k+2)}2$$ and observe that is what you were trying to prove because you have substituted $k+1$ for $n$ in your guess.

Related Question