$T_n:=$ number of ways $n$ balls(which are the same) can be distributed in different boxes such that in each box there are at least 2 balls Find recurrent formula for $T_n$
IMPORTANT: number of boxes is not limited.
Usually in problems of this kind it is easy to understand what happens with $n$-th element when it comes into play but in this case it doesn't seem to be that easy. For example, there exist situation, where if we take $n$-th ball out of box, $T_{n-1}$ can be invalid (if we took it from box where were only two elements)
 A: By considering the number of balls in the last box, we get
$$
T_n=T_{n-2}+T_{n-3}+T_{n-4}+\dots+T_2
$$
For example, if the last box contains $3$ balls, then the remaining $n-3$ balls must be put into boxes in $T_{n-3}$ ways.
You can then modify this recurrence so that it only has a bounded number of terms. If you take the above equation with $n-1$ substituted for $n$, you get
$$
T_{n-1}=T_{n-3}+T_{n-4}+\dots+T_2
$$
Now, subtracting the second from the first,
$$
T_{n}-T_{n-1}=T_{n-2}\implies T_{n}=T_{n-1}+T_{n-2}
$$
That is, $T_n$ satisfies the Fibonacci recurrence! With hindsight, you can prove this recurrence directly:

*

*If the last box has more than $3$ balls, then removing one ball from the last box leaves a distribution of $n-1$ balls.


*If the last box has $2$ balls, then removing those $2$ balls leaves a distribution of $n-2$ balls.
A: I propose a direct approach without a recurrent formula.
Suppose $n=2k$, then we can have good cases only for a number of boxes equal to $1,...,k$.
Consider $i = $ number of boxes. Now we put $2$ balls in each box by default. Then it reamains only $2k-2i$ balls that we can put as we want in the $i$ boxes.
The number of ways we can do this is easy to compute (anagrams of words with $2k-2i$ letter $A$ and $i-1$ letter $B$):
$$
\binom{2k-2i+i-1}{i-1} = \binom{2k-i-1}{i-1}
$$
The sum over $i$ is the answer to your question:
$$
T_n = T_{2k} = \sum_{i=1}^{k} \binom{2k-i-1}{i-1}
$$
The case $n=2k+1$ is really similar and it gives:
$$
T_n = T_{2k+1} = \sum_{i=1}^{k} \binom{2k-i}{i-1}
$$
