Solve the following recurrence $\left(n+1\right)a_n=na_{n-1}+1\:\:\:\:\:\forall n\ge 1\:and\:a_0\:=\:1$

Question

I am trying to resolve this recurrence

$\left(n+1\right)a_n=na_{n-1}+1\:\:\:\:\:\forall n\ge 1\:and\:a_0\:=\:1$

What i have tried is to

1. First write the homogeneous equation $a_{nh}=\frac{n}{n+1}\cdot a_{n-1}$
2. Try to solve the particular solution $a_{nP}=bn+c\:\:\:$ so then we replace and try to solve for B and C $bn+c=\frac{n}{\left(n+1\right)}\cdot b\left(n-1\right)+c+\frac{1}{n+1}\:\:\:$
3. Then if i find the solution for B and C what i would do is $a_n=a_{nh}+a_{nP}$

Then i got stuck because the only solution that i found was $b=\frac{1}{2n}$

Answer 1

We sum both sides of the equality $(n+1)a_{n}=na_{n-1}+1$ for $ n=1 , 2 ,..., N $, we have

$2a_{1}+3a_{2}+...+Na_{N-1}+(N+1)a_{N}=a_{0}+2a_{1}+3a_{2}+...+Na_{N-1}+N$ . Therefore $(1+N)a_{N}=1+N$ or $a_{n}=1$ for all integers $n\ge0$.

Answer 2

Set $b_n:=(n+1)a_n$. Then your approach is fine. Solve the homogeneous equation $b_{nh}-b_{(n-1)h}=0$. It should be easy to find a particular solution to the non-homogeneous equation. You will get a general solution for $b_n$. Plug in the initial condition $b_0=a_0=1$ and you can find the solution.

Answer 3

Induction on $n$ to prove $a_n=1, \forall{n} \in {0} \cup\mathbb{N}$

Basis: $a_0=1$ (given)

Hypothesis: $a_n=1$ for some $n \in \mathbb{N}$

Induction Step: $a_{n+1}=\frac{(n+1)a_n+1}{n+2}=\frac{(n+1).1+1}{n+2}=\frac{n+2}{n+2}=1$

Generating function method

Let's use generating function $f(x)=\sum\limits_{n\geq 0}(n+1)a_nx^n$

Now, we have, $\sum\limits_{n\geq 1}(n+1)a_nx^n=\sum\limits_{n\geq 1} na_{n-1}x^n+\sum\limits_{n\geq 1}1.x^n$

$\implies f(x)-a_0=x\sum\limits_{n\geq 0} (n+1)a_{n}x^n+\sum\limits_{n\geq 1}x^n$

$\implies f(x)-1=xf(x)+\frac{x}{1-x}$

$\implies (1-x)f(x)=1+\frac{x}{1-x}=\frac{1}{1-x}$

$\implies f(x)=\frac{1}{(1-x)^2}=\sum\limits_{n\geq 0}(n+1)x^n$

But $f(x)=\sum\limits_{n\geq 0}(n+1)a_nx^n=\sum\limits_{n\geq 0}(n+1)x^n$

$\implies a_n=1$, $\forall{n}$

Answer 4

Let $F_n=(n+1)a_n$, then we get $F_n-F_{n-1}=1$ meaning $F_n$ is an AP with common difference 1so $F_n=n+k$, use $F_0=1$ to get $k=0$. Hence $F_n=n \implies a_n =\frac{n}{n+1}$

Answer 5

Let $b_n = (n+1)a_n$, so we have $$b_n = b_{n-1} +1 $$ and $b_0 = 1$. Then it is easy to get the expression of $\{b_n\}$.

Answer 6

Observe that $$ 0=\left(n+1\right)a_n-na_{n-1}-1=\left(\left(n+1\right)a_n-(n+1)\right)-(na_{n-1}-n) $$ Hence the sequence $na_{n-1}-n$ is constant and equals to $0$ for $n=1$. Therefore $a_n=1$ for all $n$.