upper bound of a double sequence

Question

Let $\{ a_{k,m} \}$ be a doublely indexed sequence of positive numbers satisfying:
$a_{1,n}\leq \frac{1}{n+1}\quad $ and $\quad a_{k,m} \leq \frac{1}{m+1}(a_{k-1,m+1}+L a_{k-1,m+2})\quad \quad (1)$ ,
where $L$ is a positive constant and indices $k,m,n$ are non-negative integers.

My question is: what is the upper bound for $a_{n,0}$ in terms of n ?

I try to find the bound by induction using relation in $(1)$ to reduce the index $n$ in $a_{n,0}$ to $1$, but I'm not able to compute the final representation in terms of $a_{1,k} (k\geq 1)$.

Answer 1

As fedja mentioned, if $a_{k,m+1}\leq a_{k,m}$, we can easily arrive at a bound in fedja's comment. Since this may not be the case, we do need some preparations to formalize the argument.

We define $\hat{a}_{k,m}:=\text{maximal achieveble upper bound for $a_{k,m}$ from inequality (1)}$, namely, $\hat{a}_{1,n}=1/(n+1)$, and $\hat{a}_{k,m}=\frac{1}{m+1}(\hat{a}_{k-1,m+1}+L \hat{a}_{k-1,m+2})$.

Then it is easy to see from induction that $\hat{a}_{k,m+1}\leq \hat{a}_{k,m}$. Thus we deduce that
$a_{n,0}\leq \hat{a}_{n,0}\leq \frac{1+L}{1}\hat{a}_{n-1,1}\leq \frac{(1+L)^{2}}{2!}\hat{a}_{n-2,2}\leq\dots \leq \frac{(1+L)^{n-1}}{(n-1)!}\hat{a}_{1,n-1}=\frac{(1+L)^{n-1}}{n!}$.

Answer 2

The question is slightly ill-posed, since one may come up with several bounds, not just one, and it is not clear which one you will be satisfied with. In general, one looks for bounds having specific properties (among all the possible bounds), allowing one to further construct a certain reasoning. You do not specify what type of reasoning you want the bound to enable.

As you have discovered, trying to come up with a general formula for $a_{n,0}$ in terms of $a_{1,\ldots}$ is not easy at all. Fortunately, you want an upper bound, not an exact value, so when working with equalities turns out to be too difficult we shall replace them with inequalities, getting a weaker result but still a satisfying one.

Starting out with the formula you give, one immediately goes back one step to

$$a_{k,m} \le \frac 1 {(m+1)(m+2)} a_{k-2,m+2} + \left( \frac 1 {(m+1)(m+2)} + \frac 1 {(m+1)(m+3)} \right) L a_{k-2,m+3} + \frac 1 {(m+1)(m+3)} L^2 a_{k-2,m+4}$$

which is quite ugly and is probably where you got stuck. The trick is to replace each fraction with the larger fraction $\dfrac 1 {(m+1)^2}$, thus obtaining (note that the middle term contains two fractions)

$$a_{k,m} \le \frac 1 {(m+1)^2} \left( a_{k-2,m+2} + 2 L a_{k-2,m+3} + L^2 a_{k-2,m+4} \right) .$$

Note that the quantity between brackets reminds us of Newton's binomial; also, note that when you sum both indices of $a$, you get $k+m$, $k+m+1$ and $k+m+2$. This makes us suspect that after backtracking, the final expression (the one involving only terms like $a_{1,\ldots}$) will look like

$$a_{k,m} \le \frac 1 {(m+1)^{k-1}} \left( \binom {k-1} 0 a_{1,k+m-1} + \binom {k-1} 1 L a_{1,k+m} + \binom {k-1} 2 L^2 a_{1,k+m+1} + \dots + \binom {k-1} {k-1} L^{k-1} a_{1,k+m-1 + k-1} \right) .$$

In order to get rid of the $a_{1,\ldots}$ we shall use $a_{1,n} \le \dfrac 1 {n+1}$. This is good, but will still give us an ugly result, therefore we shall use one more upper bound for all these terms: $a_{1,k+m+i} \le \dfrac 1 {k+m} \ \forall 0 \le i \le k-1$. Using $\sum \limits _{i=0} ^{k-1} \binom {k-1} i L^i = (1+L)^{k-1}$ will allow us to finally write

$$\color{blue} {a_{k,m} \le \frac 1 {(m+1)^{k-1}} \frac 1 {k+m} (1+L)^{k-1}} .$$

Of course, guessing is only a part of the solution. Let us use induction on $k$ to also show that our guess is correct.

For $k=1$ we get $a_{1,m} \le \frac 1 {m+1}$ which is precisely what the problem assumes.

Assume now the above guess true for $k$ and let us prove it for $k+1$. Using the recursion given by the problem,

$$a_{k+1, m} \le \frac 1 {m+1} \left( a_{k,m+1} + L a_{k,m+2} \right) \le \frac 1 {m+1} \left( \frac 1 {(m+2)^{k-1}} \frac 1 {k+m+1} (1+L)^{k-1} + L \frac 1 {(m+3)^{k-1}}\frac 1 {k+m+2} (1+L)^{k-1} \right) .$$

Using that $\dfrac 1 {m+2}, \dfrac 1 {m+3} \le \dfrac 1 {m+1}$ and that $\dfrac 1 {k+m+2} \le \dfrac 1 {k+m+1}$ makes the last term above

$$\le \frac 1 {(m+1)^k} \frac 1 {k+m+1} (1+L)^k$$

which is precisely the induction hypothesis for $k+1$ instead of $k$.

Finally, taking $k=n$ and $m=0$ gives $\color{red} {a_{n,0} \le \dfrac 1 n (1+L)^{n-1}}$.

If you were patient enough to follow the above computations you have noted that at several moments we have sacrificed equalities and used upper bounds instead. This means that this upper bound that we have obtained is not the best, but it has the advantage that is has the simplest formula, allowing you to use it. Better upper bounds are possible, but uglier and therefore difficult to use in applications.