Well spotted!
This is due to important known properties of the binomial coefficients.
What you write as entry $d_n$ in the diagonal $D_k$ is usually written as the binomial coefficient $\binom {n-1+k-1}{k-1}$. To avoid subtracting $1$ all the time, I’ll write the pattern you found for entry $d_{n+1}$ in the diagonal $D_{k+1}$. This is
$$
\binom {n+k}k=\binom{n+k-1}k+n+1+\sum_{j=1}^{k-2}(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]
$$
(where I’ve assumed that, as discussed in the comments, you meant $x$ to represent $n$ – usually we stick with one name for a variable).
To simplify this, note that the two terms on either side of the equals sign are precisely what you get if you extend the sum down to $j=0$, so you can write this as
$$
0=n+1+\sum_{j=0}^{k-2}(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]\;.
$$
You can replace the upper limit of the sum by $n$, because any terms with $j\gt k-2$ don’t contribute since the first factor is zero and any terms with $j\gt n$ don’t contribute since the second factor is zero (there are zero ways to choose $k$ from $n$ objects when $k\gt n$); thus, equivalently,
$$
0=n+1+\sum_{j=0}^n(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]\;.
$$
Next, you can apply the basic recurrence relation for Pascal’s triangle,
$$
\binom nk=\binom{n-1}k+\binom{n-1}{k-1}\;,
$$
to replace the difference in brackets by a single binomial coefficient:
$$
0=n+1+\sum_{j=0}^n(-1)^{j+1}\binom{k-2}j\binom{n+k-j-1}{k-1}\;,
$$
or
$$
\sum_{j=0}^n(-1)^j\binom{k-2}j\binom{n+k-j-1}{k-1}=n+1\;.
$$
This is the main content of your formula, stripped of unnecessary complications. I wouldn’t call this a known equation in this exact form, but it’s a type of relationship among binomial coefficients that’s well known and often useful. You can derive it by applying the following transformations. First, use the symmetry of the binomial coefficients,
$$
\binom nk=\binom n{n-k}\;,
$$
which leads to
$$
\sum_{j=0}^n(-1)^j\binom{k-2}j\binom{n+k-j-1}{n-j}=n+1\;.
$$
Now apply the formula for negating the upper coefficient, which is
$$
\binom nk=(-1)^k\binom{k-n-1}k\;,
$$
to the second factor. (Here I’m using a generalization of the binomial coefficients to negative integers; these coefficients don’t appear in Pascal’s triangle, but they can be very useful.) This leads to
$$
(-1)^n\sum_{j=0}^n\binom{k-2}j\binom{-k}{n-j}=n+1\;.
$$
Now comes a nice relationship known as Vandermonde’s identity:
$$
\binom{m+n} r=\sum_{k=0}^r\binom mk\binom n{r-k}\;.
$$
If $m$, $n$ and $r$ are non-negative integers, this expresses the fact that choosing $r$ from $m+n$ objects can be done by choosing $k$ from $m$ of the objects and $r-k$ from the other $n$ objects. When (as in our case) $m$ and $n$ are not restricted to non-negative integers, the identity is also known as the Chu–Vandermonde identity. Applying it with $m=k-2$ and $n=-k$, and thus $m+n=-2$, leads to
$$
(-1)^n\binom{-2}n=n+1\;.
$$
And that’s just the definition of $\binom{-2}n$:
$$
\binom{-2}n=(-1)^n\binom{n-(-2)-1}n=(-1)^n\binom{n+1}n=(-1)^n\binom{n+1}1=(-1)^n(n+1)\;.
$$
Of course I applied the steps in the wrong direction, starting from your observation, but they’re all equivalences, so you can go in the other direction to derive your formula.
So, well done! You found quite a non-trivial relationship among the binomial coefficients that takes a number of important results to derive. Note that you can derive lots of similar relationships by using other negative integers instead of $-2$.
This may all be a bit much to take in – feel free to ask further questions, and let me know in the comments if you do.
The probability that the first $n-1$ steps are all downward is at least $\left(\frac25\right)^{n-1}$: If all previous steps were downward, one option above is blocked and both options below are open, so the probability for the next step to also be downward is at least $\frac25$.
If all previous steps were downward, then as shown in the question there’s some small constant probability $p$ that we will box ourselves in and end on one of the numbers directly below. (Two of the numbers at the top right of the red path shown in the image may not exist if we’re at the boundary, but that just increases the probability of ending up boxed in at the end point, since in that case we can go there directly with probability $\frac13$ instead of taking three steps with probability $\frac15\cdot\frac15\cdot\frac14$ to get there.)
Both the first $n-1$ downward steps and the $n$-th downward boxing-in step can go left or right, so we can go left or right with equal independent probability $\frac12$ in each step. Then with probability at least $p\left(\frac25\right)^{n-1}2^{-n}\binom nk=c\left(\frac15\right)^n\binom nk$ (with $c=\frac52p$) we end up at $\binom nk$, so the contribution of the $n$-th row to the expectation is at least
\begin{eqnarray}
c\left(\frac15\right)^n\sum_{k=0}^n\binom nk^2
&=&
c\left(\frac15\right)^n\binom{2n}n
\\
&\ge&
c\left(\frac15\right)^n\frac{4^n}{2n+1}
\\
&=&
c\left(\frac45\right)^n\frac1{2n+1}\;.
\end{eqnarray}
(see Wikipedia and Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$).
That’s already very close to what we need – we just have to mop up a bit more probability to increase the factor from $\frac45$ to $1$. To do that, let’s consider two cases depending on whether we’re on the boundary.
If we’re on the boundary, we can improve the bound $\frac25$ on the probability to go downward to $\frac23$, since two of the other adjacent numbers aren’t available.
If we’re not on the boundary, we can reach either number directly below by first moving sideways and then down. The probability for taking one of these two routes is $2\cdot\frac15\cdot\frac14=\frac1{10}$, since on the downward step two other options have already been used. (All the other probabilities are influenced by such sideways steps, since they take away options, but these are options we don’t want to take, so that merely increases the probabilities for the options we do want to take, so all the bounds remain valid.)
This is exactly what we need to get a lower bound of $\frac25+\frac1{10}=\frac12$ for the probability to go downward and thus a lower bound of $\frac c{2n+1}$ for the contribution from each row. It follows that the expected value of the coefficient we end up on is at least
$$
\sum_n\frac c{2n+1}=\infty\;.
$$
Best Answer
$n \choose k$ is odd, for every $k=0,1,..,n$ if and only if $n=2^m-1$ (i.e. $n$ has only 1's in its base 2 expansion).
This is proved using Lucas' theorem