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 :-)
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$.