# Solving recursive inequality involving binomial coefficients.

Let $T(n,m)$ be such that : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} T(i,m-1)$$ where $T(n,1) \leq 2^n$ and $n, m\in \mathbb{N}$.

I want to solve this recursive inequality in order to find a close form upper bound for $T(n,m)$.

The well known binomial theorem (more info on wikipedia here and here) teach us that : $$(a+b)^n = \sum\limits_{i=0}^{n}{{n}\choose{i}}a^{n-i}.b^i$$

I think that using this theorem we can prove that $$T(n,m) \leq 2^{nm}$$ but I'm not 100% sure if what I did was correct... And I would appreciate if someone could give a look at my proof below which is done by recurrence. Thanks :-)

Proof by recurrence :

At the lowest rank $m=1$ : $T(n,m) \leq 2^{nm}$ is trivially true, since $T(n,1) \leq 2^n$ is given.

For a rank $m > 1$ :

• At rank $m-1$ : we suppose $T(n,m-1) \leq 2^{n(m-1)}$ true.
• And at rank $m$, we have by definition : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} T(i,m-1)$$
• Thus : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} 2^{i(m-1)}$$
• That we can rewrite into : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} (2^{m-1})^i$$
• Since by the binomial theorem we have : $$(a+b)^n = \sum\limits_{i=0}^{n}{{n}\choose{i}}a^{n-i}.b^i$$
• And setting $b=2^{m-1}$ and $a=1$ we obtain : $$T(n,m) \leq (2^{m-1} + 1)^n$$
• And since $(2^{m-1} + 1)^n \leq (2^{m-1} + 2^{m-1})^n$ we get : $$T(n,m) \leq 2^{mn}$$

End of proof

I still have a little doubt on the scope of validity of the proof, since there are two variables and I did the recurrence only on $m$. Is it also proven for every $n$ ? Is it correct to say that for any $n, m\in \mathbb{N}$ we have $T(n,m) \leq 2^{mn}$.

If what I did is correct, it seems that this method may be easily generalized and applied on a lot of different types of combinatorics problems leading to similar recurence formulas involving binomial coefficients... Could someone proofcheck my proof :-) and if similar technics already exist, maybe someone could give me the reference of a book or a tutorial explaining it ?

Thank you very much, Luz :-)

• Just to clarify, are you looking to find the best bound possible, or will any bound be okay? The best bound possible would be obtained by replacing the $\leq$ signs with $=$ and trying to find an explicit expression for $T(n,m)$. – user49640 Apr 25 '17 at 2:32
• well if you can propose a tight bound, you will make me happy :-) so ok for replacing $\leq$ by $=$. And what about the recursive proof ? Do you think it is correct and that $T(n,m) \leq 2^{mn}$ for all $m,n \in \mathbb{N}$ ? – Luz Apr 25 '17 at 13:10
• Your proof looks correct to me. But I think the same method can be used to prove $T(n,m) \leq (m + 1)^n$, and that bound would be tight. – user49640 Apr 25 '17 at 17:32
• Indeed you are right. Thank you :-) To prove that $T(n,m) \leq (m+1)^n$ : we see that at rank $m=1$ it is true since $T(n,m) \leq (1+1)^n$ and $T(n,m) \leq 2^n$ is given. At rank $m-1$ we suppose $T(n,m-1) \leq m^n$ true. And following the same method, we can use the binomial theorem on $T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} m^i \times 1^{n-i}$ to obtain $T(n,m) \leq (m + 1)^n$. – Luz Apr 26 '17 at 8:36

As told in the previous comment : The proof looks correct. Furthermore, a better upper bound $(m+1)^n$ may be proposed for $T(n,m) = \sum\limits_{i=0}^{n}{{n}\choose{i}} T(i,m-1)$ where $T(n,1) = 2^n$ and $n, m\in \mathbb{N}$.
We can prove that $T(n,m) = (m+1)^n$ by proving at rank $m=1$ that it is true since $T(n,m) = (1+1)^n$ and $T(n,m) = 2^n$ is given. And at rank $m-1$ we suppose $T(n,m-1) = m^n$ true. And following the same method, we can use the binomial theorem on $T(n,m) = \sum\limits_{i=0}^{n}{{n}\choose{i}} m^i \times 1^{n-i}$ to obtain $T(n,m) = (m + 1)^n$.