Finding the general formula for a sequence I wanna find the general formula for the sequence below:
$$
U(n+2)=U(n+1)/(n+2)+nU(n)/(n+2).$$
I know how the Fibonacci sequence is derived either by linear algebra or some other method but I can't, how can I derive this?
With the initial conditions  U0=U1=1 
 A: $$(n+2)U_{n+2}=U_{n+1}+nU_n$$
The generating function for this sequence is
$$f(z)=U_0+U_1z+U_2z^2+U_3z^3+\dots$$
Hence we have
$$f'(z)=U_1+2U_2z+3U_3z^2+\dots$$
$$z^2f'(z)=U_1z^2+2U_2z^3+3U_3z^4+\dots$$
$$f'(z)-z^2f'(z)=U_1+2U_2z+(3U_3-U_1)z^2+(4U_4-2U_2)z^3+\dots$$
So applying $U_{n+1}=(n+2)U_{n+2}-nU_n$ and factoring gives
$$(1-z^2)f'(z)=U_1+2U_2z+U_2z^2+U_3z^3+\dots$$
$$(1-z^2)f'(z)=U_1+2U_2z+f(z)-U_0-U_1z$$
$$(1-z^2)f'(z)-f(z)=U_1-U_0+(2U_2-U_1)z$$
We have that $2U_2=U_1+0U_0$ hence $U_0=U_1=1$ and $U_2=\frac12$ which gives
$$(1-z^2)f'(z)-f(z)=1-1+\left(2\left(\frac12\right)-1\right)z=0$$
$$f'(z)=\frac{f(z)}{1-z^2}$$
$$\frac{f'(z)}{f(z)}=\frac1{1-z^2}$$
$$\frac{\mathrm{d}}{\mathrm{d}z}\ln{(f(z))}=\frac1{1-z^2}$$
$$\ln{(f(z))}=\int\frac1{1-z^2}\mathrm{d}z$$
$$\ln{(f(z))}=\ln{\left(\sqrt{\frac{1+z}{1-z}}\right)}$$
$$\therefore f(z)=\sqrt{\frac{1+z}{1-z}}$$
As suggested by @achille hui this gives
$$U_n=4^{-\lfloor n/2\rfloor}\binom{2\lfloor n/2\rfloor}{\lfloor n/2\rfloor}$$
or equivalently,
$$U_n=\frac{(2\lfloor n/2\rfloor-1)!!}{2^{\lfloor n/2\rfloor}\lfloor n/2\rfloor!}$$
where $n!!$ denotes the double-factorial function.
A: I tried to use the generating function method explained by Peter Foreman and Achille Hui.  Unfortunately, my brain seems to be on strike today, and I couldn't make it come out.  I solved the problem with an ad hoc method that I was ashamed to post at first, but on reflection, I think it may be of interest.
I started by computing a few values of the sequence and I got
0 1  
1 1
2 1/2
3 1/2
4 3/8
5 3/8
6 5/16
7 5/16
8 35/128
9 35/128
10 63/256
11 63/256
12 231/1024
13 231/1024
14 429/2048
15 429/2048
16 6435/32768
17 6435/32768
18 12155/65536
19 12155/65536
20 46189/262144
21 46189/262144

It's an obvious guess that $u_{2n+1}=u_{2n}$ so assuming this is true, and letting $v_m=u_{2m}$ I got $$ v_{m+1}={2m+1\over2m+2}v_m,\ v_0=1$$ so that
$$u_{2m}=v_m=1\cdot\frac12\cdot\frac34\cdot\frac56\cdot\cdots\cdot{2m-1\over2m}={(2m-1)!!\over(2m)!!}$$
Of course, one still has to verify that the original guess $u_{2n+1}=u_{2n}$ holds in general.
