I want to analyse the following expression for $x \geq 0$:

$$ \sum_{k = 0}^n (-1)^{k+n} \binom{n+k}{2k} x^k $$

I expect and want to prove that for $x \geq 4$, the expression tends to infinity as $n \to \infty$. I tried coming up with a closed expression, however found it difficult to cope with the upper $k$ in the binomial coefficient.


First we try to find a closed form of the sum, preferably one whose asymptotics can be classified. Let $f_n$ be your sum. Then Sister Celine / Zeilberger's algorithm says that $$f_n = (x-2) f_{n-1} - f_{n-2}.$$ The roots of the characteristic equation of this recurrence are $$\rho_{1,2} = -1 + \frac{1}{2} x \pm \frac{\sqrt{x^2-4x}}{2}.$$ We are looking for a closed expression of the form $$c_1\rho_1^n+c_2\rho_2^n$$ using $f_0 = 1$ and $f_1 = x-1$ and solving for $c_{1,2}$ we get that $$c_{1,2} = \frac{1}{2} \pm \frac{1}{2} \frac{\sqrt{x^2-4x}}{x-4}$$ for an end result of $$f_n = \left(\frac{1}{2} + \frac{1}{2} \frac{\sqrt{x^2-4x}}{x-4}\right) \left(-1 + \frac{1}{2} x + \frac{\sqrt{x^2-4x}}{2}\right)^n \\+ \left(\frac{1}{2} - \frac{1}{2} \frac{\sqrt{x^2-4x}}{x-4}\right) \left(-1 + \frac{1}{2} x - \frac{\sqrt{x^2-4x}}{2}\right)^n.$$ We will now study the two exponential terms, showing that the second one vanishes and the first one produces exponential growth. Start by observing that $$\frac{\sqrt{x^2-4x}}{2} = \frac{1}{2} x \sqrt{1-4/x}$$ which for $x\ge 4$ can be expanded into a convergent asymptotic series $$\sqrt{1-4/x} = \sum_{q\ge 0} (-1)^q {1/2\choose q} \left(\frac{4}{x}\right)^q \sim 1-\frac{2}{x} - \frac{2}{x^2}.$$ Therefore $$-1 + \frac{1}{2} x - \frac{\sqrt{x^2-4x}}{2} = -1 + \frac{1}{2} x - \frac{x}{2} \sqrt{1-4/x} \\ \sim -1 + \frac{1}{2} x - \frac{x}{2} \left(1-\frac{2}{x} - \frac{2}{x^2}\right) = \frac{1}{x}.$$ We see that the second term behaves like $1/x^n$ for $x\ge 4$ and vanishes as claimed. Note that it is critical in this argument that the first terms of the series expansion of the root get canceled.

Finally we have for the first term that $$-1 + \frac{1}{2} x + \frac{\sqrt{x^2-4x}}{2} = -1 + \frac{1}{2} x + \frac{x}{2} \sqrt{1-4/x} \\ \sim -1 + \frac{1}{2} x + \frac{x}{2} \left(1-\frac{2}{x} - \frac{2}{x^2}\right) = x - 2 - \frac{1}{x}.$$ This is approximately $x-2$ and its $n$th powers go to infinity as claimed. The constants in front of the two exponential terms are independent of $n$ and do not influence the asymptotic behaviour.

Addendum. This matches the output from Wolfram Alpha.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.