Finding closed formula and proving it by induction

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 \leq 5 \\ F(n-5)+n+1, & \mbox{if } n > 5 \end{cases}$$

Note that $n=5+j$ , for $k$ and $j$ integers, such that $k\geq0$ and $0\leq j\leq4$

This is what I got so far:

$F(n) = F(n-5) + n + 1 = (F(n-10)) + (n-5) + 1) + n + 1 = (F(n-15)) + (n-10) + 1) + (n-5) + 1) + n + 1$

So I chose an $n$ not too large but also not too small to expand the recurrence as follows:

$F(28) = F(23) + 28 + 1 =(F(18) + 23 + 1)+28+1 =(F(13)+18+1)+28+1 =F(8) + 18 + ... =F(3)+8+... =((((1+8+1)+13+1) + 18 + 1) + 13 + 1)+28+1$

Therefore,

$F(5k+j) = (((...(1+5\times1+j+1)+5\times2+j+1)...)+5-k+j+1$

Finally,

$\begin{align}F(5k+j)& = 1+5\times1+j+1+5\times2+j+1+...+5k+j+1\\ & = 1+j\times n+5n(1+2+3+...+k)+n \\ & = 1+n\left(5\sum_{i=1}^{n}i + j + 1\right)\end{align}$

I'd some help to prove my closed formula by induction and to adjust the formula for the case $j = 0$. That is, my formula will have two cases (when $j> 0$ and when $j = 0$ is almost the same, but with an adjustment).

Answer 1

Such a closed formula is:$$F(n)=\alpha\left(\left\lceil\frac n5\right\rceil\right)+\left(\left\lceil\frac n5\right\rceil-1\right)\left(n+4-5\left\lceil\frac n5\right\rceil\right),$$with$$\alpha(n)=\frac{5n^2-n-2}2.$$Note that $\alpha(1)=1$ and that$$n\in\mathbb{N}\setminus\{1\}\implies\alpha(n)-\alpha(n-1)=5n-3.\tag1$$

It is clear that $F(n)=1$ when $n\in\{1,2,3,4,5\}$. On the other hand, if $n>5$, then $F(n)-F(n-5)$ is equal to\begin{multline}\alpha\left(\left\lceil\frac n5\right\rceil\right)-\alpha\left(\left\lceil\frac{n-5}5\right\rceil\right)+\\+\left(\left\lceil\frac n5\right\rceil-1\right)\left(n+4-5\left\lceil\frac n5\right\rceil\right)-\left(\left\lceil\frac{n-5}5\right\rceil-1\right)\left(n-1-5\left\lceil\frac{n-5}5\right\rceil\right).\end{multline}Now, using $(1)$ and the fact that $\left\lceil\frac{n-5}5\right\rceil=\left\lceil\frac n5\right\rceil-1$, we get that the previous expression is equal to$$5\left\lceil\frac n5\right\rceil-3+\left(\left\lceil\frac n5\right\rceil-1\right)\left(n+4-5\left\lceil\frac n5\right\rceil\right)-\left(\left\lceil\frac n5\right\rceil-2\right)\left(n-5\left\lceil\frac n5\right\rceil+4\right).$$Now, a simple algebraic computation shows that this is just $n+1$. And we're done.

Answer 2

Define $\,n:=5m+j\,$ with $\,m\in\mathbb{N}_0\,$ and given $\,j\in\{1,2,3,4,5\}\,$ .

Then we get $\,\displaystyle F(5m+j)=5\frac{m(m+1)}{2}+(j+1)m+1\,$ .

Test: $\,F(j)=1\,$ (o.k.)

And: $\,F(5m+j)-F(5(m-1)+j)=5m+j+1\,$ which is $\,F(n)-F(n-5)=n+1\,$ .