Some grid

sol

Generalization for $n$ squares (recognized from the pattern) -

$f\left( n \right) ={ F }_{ 2n+2 }$

where ${ F }_{ n }$ is ${ n }^{ th }$ number in Fibonacci Series.

Here's a different approach and different formula.

Suppose you are taking $k$ diagonal steps, then your path length is $n + k + 1$ . The important point to note is each diagonal step must precede exactly 1 down step and succeed exactly 1 down step. Therefore there is total $2 \times k + 1$ down and diagonal steps.

Let us name the steps as follows

• R - Right step
• D - Down step
• Di - Diagonal step

Suppose we are taking 1 diagonal step, then we can represent this as P D Q Di R D S . Where P , Q , R and S are zero or more right steps.

If we will take $k$ diagonal steps then the order of down and diagonal steps is always the same. Therefore we just need to find how many ways we can place the diagonal and down steps in $n + k + 1$ places. And the remaining empty spaces can be filled by right steps.

$\therefore$ Total number of ways to reach to the lower right corner from the upper left corner in $n$ square figure $= \sum_{k = 0}^n {n + 1 + k \choose 2 k + 1}$

To compute quickly the general formula $F_{2n+2}$ , use $F_k\thickapprox\displaystyle \frac{\phi^k}{\sqrt{5}}$ with $\phi=\frac{1+\sqrt{5}}{2}$ .

Here, it gives $3.07, 8.02, 21.01, \cdots$ and $F_{2·7+2}\thickapprox987.0002$ .

Define $f(n)$ to be the number of paths from the top-left corner to the bottom-right corner in a grid of $n$ squares. Note that $f(0) = F_2 = 1, f(1) = F_4 = 3$ , and so we argue that $f(n) = F_{2n+2}$ , where $F_n$ is the $n$ th Fibonacci number $1,1,2,3,\dots$ .

Now, we can see that $F_{2n + 2} - 2F_{2n} = F_{2n-1} = F_{2n} - F_{2n-2}$ , so it is sufficient to show that $f(n)-2f(n-1) = f(n-1) - f(n-2)$ . So we show that the two sides count the same number of paths.

Both count the paths that avoid the vertex $C$ to the right of $A$ . The left-hand side starts with all paths and removes the two subcases that go through $C$ . The right-hand side is the number of paths starting at $C$ and moving down in the first step, which is equivalent to the number of paths starting at the vertex below $C$ , which in turn is equivalent to the number of paths that avoid $C$ .

$A_n=F_{2n+3}$ , where $F_n$ is the $n^{th}$ Fibonacci number in the sequence: $(0,1,1,2,3,5,...)$