3
$\begingroup$

Let $x_n(0)=1$, $$ x_n(N+1) = \frac{1}{N+1}\sum_{k=0}^N \sum_{j=1}^n x_j(k)x_{n+1-j}(N-k) + \frac{10}{N+1} x_{n+1}(N) , \quad\quad N\ge 0 . $$ So the recursion is on $N$, and at each level, we compute all $x_n(N)$, $n\ge 1$, before continuing. The question is whether $$ \limsup_{N\to\infty} \left( x_1(N) \right)^{1/N} < \infty . $$

Numerical results would also be appreciated, and maybe a CAS could be useful here also.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Consider the generating function: $$F(z,t) := \sum_{n\geq 1}\sum_{N\geq0} x_n(N) z^{n-1} t^N.$$ Then $F(z,0)=\frac1{1-z}$ and $$\frac\partial{\partial t} F(z,t) = F(z,t)^2 + 10F(z,t).$$ Solving this differential equation, we get $$F(z,t) = \frac{10}{(11-10z)e^{-10t} - 1}$$ and thus $$F(0,t) = \frac{10}{11e^{-10t} - 1}.$$

Now, \begin{split} x_1(N) &= [t^N]\ F(0,t) = [t^N]\ \frac{1}{1 + \frac{11}{10}(e^{-10t}-1)} \\ &= \sum_{k=0}^N [t^N]\ \left(-\frac{11}{10}\right)^k(e^{-10t}-1)^k \\ &= \sum_{k=0}^N \left\{ N\atop k\right\} \frac{k!}{N!} (-10)^{N-k} 11^k. \end{split} Bounding Stirling numbers of second kind from the above, we have \begin{split} x_1(N) &\leq \sum_{k=0}^N \frac{(-10)^{N-k} 11^k}{(N-k)!} &\approx 11^N e^{-10/11} \end{split} implying that $$\limsup_{N\to\infty} \left( x_1(N) \right)^{1/N} < 11.$$

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ In fact by some theory of differential equations with analytic coefficients I assume we don't even need to know the actual solution to conclude that the radius of convergence is positive. $\endgroup$
    – Aleksei Kulikov
    Commented Oct 17 at 22:07
  • 1
    $\begingroup$ Ok, I've corrected the expansion and corresponding bound, please check it out. $\endgroup$
    – Max Alekseyev
    Commented Oct 17 at 22:35
  • 1
    $\begingroup$ @MaxAlekseyev: I think it's still not quite right, the last term of the ODE should be $10F/z$, to incorporate the shift to $n+1$ in the index. This may actually be a problem since you want to take $z=0$ later. I've accepted your answer anyway because the general idea is helpful for me and the question is really a toy version of my actual problem anyway, so the fine details are not crucial. Thank you for your help. $\endgroup$
    – Christian Remling
    Commented Oct 18 at 1:49
  • 2
    $\begingroup$ @MaxAlekseyev: You can fix it as follows: replace the last term of the recursion by $10(n+1)x_{n+1}(N)/(N+1)$. Obviously, the new sequence bounds the old one. Now your method gives a PDE for $F$ that you can still solve explicitly (or use Cauchy-Kovalevskaya). $\endgroup$
    – Christian Remling
    Commented Oct 18 at 13:25
  • 1
    $\begingroup$ @ChristianRemling: Thanks for spotting another glitch, and it's great you figured out how to overcome it. The corrected ODE is also solvable, but it's more technically challenging to extract $F(0,t)$ from it. Anyway, since this particular problem is a toy one, I'll leave my answer as is. $\endgroup$
    – Max Alekseyev
    Commented Oct 18 at 18:04

You must log in to answer this question.

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