Asymptotic behaviour of recurrence relation I have the following recurrence relation
$$u_0=1, u_1=5$$
$$n^3u_n-(34n^3-51n^2+27n-5)u_{n-1}+(n-1)^3u_{n-2}=0, \forall n \geq 2$$
for which I know that
$$b_n=\sum_{k=0}^n \binom{n}{k}^2\binom{n+k}{k}^2$$
is the solution.
How can I prove that there exists a positive constant $A$ such that $b_n \sim A \alpha^n n^{-3/2}$
where $\alpha$ is the greatest root of the polynomial $x^2-34x+1$?
 A: The below uses some special function theory to prove
$$ u_n:=\sum_{k=0}^n \binom{n}{k}^2\binom{n+k}{k}^2 \sim A\, (n+1/2)^{-3/2}\Big(17+12\sqrt{2}\Big)^n $$ 
where $A=(2\,\sqrt{2}\,\pi)^{-3/2}(3+2\,\sqrt{2})$ and $17+12\sqrt{2}$ is
indeed the larger root of the polynomial $x^2 - 34\,x + 1=0$, as stated in the problem.
Start with the Legendre polynomial expression 
$$ P_n(1+2x) = \sum_{k=0}^n \binom{n}{k} \binom{n+k}{k} x^k $$
Use the Hadamard product (I prove it in MSE 3526636) to get
$$u_n=\frac{1}{2\pi}\int_0^{2\pi} P_n(1+2e^{i\,\theta}) P_n(1+2e^{-i\,\theta})\, d\theta$$ 
Now use the integral relationship for a product of Legendre polynomials
$$P_n(z)\,P_n(w) = \frac{1}{\pi} \int_0^\pi P_n(z\,w + \sqrt{(1-z^2)(1-w^2)}\,\cos(\phi) )\, d\phi $$
Insert this integral into the penultimate equation, do some algebra, and use a symmetry argument for the outer integral to conclude
$$ u_n = \frac{1}{\pi^2} \int_0^\pi d\theta \int_0^\pi d\phi \, P_n(5+4 \, \cos{\theta}+8\cos{(\theta/2)}\,\cos{\phi} ) $$
This double integral is that which will have performed on it asymptotic analysis.  Note that the argument of the $P_n(\cdot)$ is $\ge$ 1.  Thus the well-known asymptotic expansion next should be used.
$$ P_n(\cosh{t}) \sim \Big(\frac{t}{\sinh(t)}\Big)^{1/2} I_0\big((n+1/2)t\big)$$
For our problem, $t=\cosh^{-1}(5+4 \, \cos{\theta}+8\cos{\theta}\,\cos{\phi})$ (the inverse hyperbolic cosine).
$I_0\big(z\big)$ is the modified Bessel function and has for real positive argument the asymptotic expansion (first term only)
$$ I_0\big(z\big) \sim \frac{ \exp{(z)} }{\sqrt{2 \pi z}}\,. $$ 
This expansion is very useful. Looking at plots, it appears that the integrand (over $\theta$) is peaked at the origin.  As with many asymptotic problems, you'd like to get an integrand that looks like a gaussian, get the amplitude and width of the gaussian, extend the limits from a finite range ($\pi$ in our case) to $\infty$ so that an analytic result can be obtained.  That's exactly the strategy, but in 2D.  
The factor raised to the 1/2 power in the penultimate equation is slowly varying, so we bring it outside the integrals, but evaluate it $\theta=0$ and $\phi=0$ (in big $\big(\cdot\big)$ below).
Thus,
$$ u_n \sim \frac{1}{\pi^2} \frac{1}{\sqrt{2\pi(n+1/2)}}\big( \frac{2^{-5/4}}{\sqrt{3}}\big) \cdot $$
$$ \cdot  \int_0^\pi d\theta \int_0^\pi d\phi \,
\exp{\big((n+1/2)\cosh^{-1}(5+4\,\cos{\theta} + 8\cos{(\theta/2)} \cos{\phi} )\big) } $$
Expand the argument of the exponential to order $\theta^2$ and $\phi^2.$  Extend the limits of the integrals to $\infty.$ Do the integrals explicitly.  One finds that
$$u_n \sim \frac{2^{-7/4}}{\sqrt{3(n+1/2)}\pi^{5/2}} \int_0^\infty d\theta \int_0^\infty d\phi \cdot$$
$$\cdot \exp{\big( (n+1/2)(\cosh^{-1}(17) - \frac{ \phi^2}{3\sqrt{2}} 
 - \frac{ \theta^2}{4\sqrt{2}}-5\frac{\theta^2 \phi^2 }{288 \sqrt{2} }  \big)}
$$
$$ = \sqrt{\frac{3}{5}}\frac{\exp{\big( (n+1/2)(\cosh^{-1}(17) 
+ 6\sqrt{2}/5 ) \big)}}{2 \pi^2 (n+1/2)} K_0\big( (n+1/2)6\sqrt{2}/5 \big) $$
where $K_0(\cdot)$ is the Macdonald function.
Use the asymptotic formula 
$$ K_0\big(z) \sim e^{-z}\sqrt{ \frac{\pi}{2z} } .$$
Algebra (including hyperboic trig ID's) completes the proof.
That the Legendre polynomials are used is actually quite natural.  One proof of
the irrationality of $\zeta(3)$ uses them explicitly.
For comparison: with $n=30$, the difference between the sum and its asymptotic approximation is about 1%.  For $n=301,$ about 0.1%.
