I would like to know how the left hand side of the equation is achieved. In particular why the $\frac{1}{2}$ is there. I don't understand how one can get from the left to the right side.
$$ \sum_{k=0}^{d} \binom{2d+1}{k} = \frac{1}{2} \cdot 2^{2d+1} $$
I have looked at this wikipedia entry, but it does not help me, since I do not understand why the $\frac{1}{2}$ appears.
Assuming you know that $$ \sum_{k=0}^{2d+1}\binom{2d+1}{k}=2^{2d+1} $$ and $$ \binom{2d+1}{k}=\binom{2d+1}{2d+1-k} $$ transform the sum as follows $$ \sum_{k=0}^{2d+1}\binom{2d+1}{k}=\sum_{k=0}^{d}\binom{2d+1}{k}+\sum_{k=d+1}^{2d+1}\binom{2d+1}{k}\\ =\sum_{k=0}^{d}\binom{2d+1}{k}+\sum^{2d+1}_{k=d+1}\binom{2d+1}{2d+1-k}\\ =\sum_{k=0}^{d}\binom{2d+1}{k}+\sum_{k=0}^{d}\binom{2d+1}{k}\\ $$ to get the result. In the last step we have used the substitution $k\to2d+1-k$.