3
$\begingroup$

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 <n$, 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).

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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}. $$

$\endgroup$
2
  • $\begingroup$ 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(?) $\endgroup$
    – ploosu2
    Oct 8, 2018 at 21:09
  • $\begingroup$ I asked this follow up question about the sum as a new question: math.stackexchange.com/questions/2949108/… $\endgroup$
    – ploosu2
    Oct 9, 2018 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .