# Recurrence $a_j = \frac{n}{n-j} + \frac{j}{n-j} a_{j-1}$

Let $$n\in \mathbb{N}$$. How to solve the recurrence

$$a_j = \frac{n}{n-j} + \frac{j}{n-j} a_{j-1}$$

for $$1\leq j , and $$a_0=1$$?

I calculated it for some $$n$$s:

$$n=2: [1, 3]$$
$$n=3: [1, 2, 7]$$
$$n=4: [1, \frac{5}{3}, \frac{11}{3}, 15]$$
$$n=5: [1, \frac{3}{2}, \frac{8}{3}, \frac{13}{2}, 31]$$
$$n=6: [1, \frac{7}{5}, \frac{11}{5}, \frac{21}{5}, \frac{57}{5}, 63]$$
$$n=7: [1, \frac{4}{3}, \frac{29}{15}, \frac{16}{5}, \frac{33}{5}, 20, 127]$$

It looks like $$a_{n-1} = 2^n - 1$$.

I tried to use generating function $$A(x) = \sum_{k=0}^{n-1} a_k x^k$$ and got

$$(n-x)A(x) - 2xA'(x) = n\frac{1-x^n}{1-x}-(n-1)a_{n-1}x^{n-1} - a_{n-1}x^n$$

but don't know how to solve this or if it's correct (it's highly probable I made a mistake somewhere).

From the recurrence relation, it is easy to check that

$$\binom{n-1}{j} a_j - \binom{n-1}{j-1}a_{j-1} = \binom{n}{j}.$$

Therefore

$$a_j = \frac{\sum_{k=0}^{j} \binom{n}{k}}{\binom{n-1}{j}}.$$

Addendum. By a different method, one can also prove that

$$a_j = n \int_{0}^{1} (1-u)^{n-1-j} (1+u)^j \, du = \sum_{k=0}^{j} \binom{j}{k} (-1)^{j-k}2^k \frac{n}{n-k}.$$

• Thank you for the answer. It helped me a lot, but now I'm also stuck with the sum $s_n = \sum_{j=0}^{n-1} a_j$. I'm trying to prove: $s_n = 2^{n-1}\sum_{j=0}^{n-1}\frac{1}{{n-1}\choose{j}}$. I tried induction, but no success. I don't know, maybe I should ask another question for this(?) Oct 8, 2018 at 21:09
• I asked this follow up question about the sum as a new question: math.stackexchange.com/questions/2949108/… Oct 9, 2018 at 20:51