Find a closed form for this recurrence relation

Question

For some value of $k$, $a_j=0$ for all $j\leq k$. Then, for $n\geq 1$,

$$a_{n+k}=\frac{n}{n+k}-\frac{1}{n+k}\sum_{i=k+1}^{n+k}a_i$$

What is a closed form for $a_k$?

I found that $$a_{n+k}=\frac{n}{n+k}-\frac{1}{n+k}a_{n+k}-\frac{1}{n+k}\sum_{i=k+1}^{n+k-1}a_i$$ so that $$\frac{n+k+1}{n+k}a_{n+k}=\frac{n}{n+k}-\frac{1}{n+k}\sum_{i=k+1}^{n+k-1}a_i$$ and $$a_{n+k}=\frac{n}{n+k+1}-\frac{1}{n+k+1}\sum_{i=k+1}^{n+k-1}a_i$$ But I don't know where to go from here. I calculated the first few terms, but I couldn't find a pattern. Can anyone help me out?

Cesareo · Answer 1 · 2021-03-18T18:33:53.083

2

$$ \cases{ (n+k)a_{n+k}=n-\sum_{i=k+1}^{n+k}a_i\\ (n+k-1)a_{n+k-1}=n-1-\sum_{i=k+1}^{n+k-1}a_i } $$

after subtraction

$$ (n+k)a_{n+k}-(n+k-1)a_{n+k-1} = 1-a_{n+k}\Rightarrow (n+k+1)a_{n+k}-(n+k-1)a_{n+k-1} =1 $$

now making $m = n+k$ we have

$$ (m+1)a_m-(m-1)a_{m-1}=1 \Rightarrow a_m = \frac{c_0}{m(m+1)}+\frac 12 $$

or

$$ a_{n+k} = \frac{c_0}{(n+k)(n+k+1)}+\frac 12 $$

edited Mar 18 '21 at 18:33

answered Mar 18 '21 at 16:27

Cesareo

33,252

Thank you! What is $c_0$? – Randy Mulligan Mar 18 '21 at 16:36
This constant is to be defined according to the initial conditions. – Cesareo Mar 18 '21 at 16:44
I'm sorry—I just realized there was a small typo in my statement of the problem ($\frac{k}{n+k}$ should have been $\frac{n}{n+k}$). I've updated the question. Your answer more or less translates, right? – Randy Mulligan Mar 18 '21 at 16:53
The answer was modified accordingly. – Cesareo Mar 18 '21 at 18:34

Find a closed form for this recurrence relation

1 Answers1