# Finding distinct possible values in binomial tree

I wonder how to solve this problem. Lets say we have a binomial tree with the following parameters:

$$u=1.25,\ d = 1/u,\ T=15$$.

How many distinct possible values are there for $$X_{7}$$?

• $d=1/u$ tells you it is a recombining tree. So there is one choice for $S_0$, two choices for $S_1$ (up and down), three choices for $S_2$ (up up, middle and down down), ... looks to me like there are $N+1$ choices for $S_N$. But draw the diagram to be sure... – noob2 Sep 14 '19 at 23:47

Noob2 has given the answer, a recombining tree has $$N+1$$ nodes after $$N$$ time points. In our case, you have $$8$$ distinct possible values after $$7$$ time steps. I will next illustrate the difference between a recombining and non-recombining tree.
For a binomial tree, if $$u=\frac{1}{d}$$, then an up-move followed by an down-move gives the same result as a down-move followed by an up-move (since $$ud=1$$): $$S_0ud=S_0du=S_0$$. This is a huge numerical advantange since the amount of potential nodes grows only linearly with the number of time steps.
If $$ud\neq1$$, then the order of up- and down-moves occurrring does matter and the amount of nodes grows exponentially. In particular, $$S_0ud\neq S_0du\neq S_0$$. After $$N$$ time steps, there are $$2^N$$ distinct nodes. So the difference between recombining and non-recombining is (for your example of $$N=7$$) the difference between $$7+1=8$$ and $$2^7=128$$. For numerical implementation, the former is of course much easier and less costy: just set $$N=100$$. Then, a recombining tree has $$101$$ nodes but a non-recombining tree has roughly $$10^{30}$$ nodes.
The bottom line ist that a recombining tree re-uses'' nodes it has already created and comes back to them. A non-recombining tree however creates for every existing node two new ones which leads to exponential grow. The same issue of (non-)recombining trees equally applies to the trinomial trees where you allow for an up/middle/down-move.
This image illustrates the amount of nodes of a recombining tree (the case you have since $$ud=1$$) This image illustrates the amount of nodes for a non-recombining tree 