If $F(1)=1 $ and $F(n)=F(n-1)+n$. Prove that $F(n)=\frac{n(n+1)}{2}$

Question

Find a closed formula for the recurrence below. Then, prove by induction that the formula found is correct.

$$F(n) = \begin{cases} 1, & \mbox{if } n = 1 \\ F(n-1)+n, & \mbox{if } n > 1 \end{cases}$$

(Input, output): (1,1)(2,3)(3,6)(4,10)(5,15)(6,21)(7,28)(8,36)

Closed formula: $$F(n) = \frac{1}{2}(n+1)$$

How to prove that closed formula by induction?

Answer 1

Ofc the formula for recurrence relation is $\frac{n(n+1)}{2}$ as you add $n+1$ to $F(n)$ to obtain $F(n+1)$.

Induction proof:

Statement: $F(n)=\frac{n(n+1)}{2} \text{for all }n \ \text{in } \mathbb{N}$.

$P(1)$ is true as $1=(1)(1+1)/2$.

Assume that $P(k)$ is true i.e. $F(k)=\frac{k(k+1)}{2}$. Then,

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