Moving from $(0,0)$ to $(5,5)$ without right angles 
In a Cartesian coordinate system, we can move from $(a,b)$ to $(a+1,b) , (a,b+1)$ and $(a+1,b+1)$, but there must be no right angle occur if we draw lines during the move. In how many ways can we do that so that we start from $(0,0)$ and end at $(5,5)$?

I found solution in AoPS but they just use brute-force method. Can anyone give some hints please. Thank you!
Also, I think that this problem is AIME , but I don’t know the year.
 A: Generating function approach.
Let $H(x,y)$, $V(x,y)$ and $D(x,y)$ be the generating functions of the paths which ends at $(n,m)$ with an horizontal step, a vertical step, or a diagonal step respectively.
Then the following linear relations hold
$$\begin{cases}
H=x(H+D)\\
V=y(V+D)\\
D-1=xy(H+V+D)
\end{cases}
$$
By solving the system, we find that the generating function of all the paths is
$$F(x,y)=H(x,y)+V(x,y)+D(x,y)=\frac{1-xy}{1-x-y+x^2y^2}.$$
Hence the number of paths from the origin to $(n,n)$ for $n\geq 0$ is
$$[x^ny^n]\frac{1-xy}{1-x-y+x^2y^2}=1, 1, 3, 9, 27, 83, 259, 817, 2599, 8323, 26797,\dots.$$
Therefore, for $n=5$, the answer is $83$.
The sequence appears in OEIS as A171155 and, according to the references, the diagonal of $F(x,y)$ is
$$\sqrt{\frac{1-x}{1-3x-x^2-x^3}}.$$
A: If I understand the problem correctly, and you let $\ n_h(x,y)\ $ be the number of paths from $\ (0,0)\ $ to $\ (x,y)\ $ with final step horizontal from $\ (x-1,y)\ $, $\ n_v(x,y)\ $ the number with final step vertical from $\ (x,y-1)\ $, and $\ n_d(x,y)\ $ the number with final step diagonal from $\ (x-1,y-1)\ $ then $\ n_h, n_v, n_d\ $ must satisfy the following recursions
\begin{align}
n_h(x,y)&=n_h(x-1,y)+n_d(x-1,y)\\ n_v(x,y)&=n_v(x,y-1)+ n_d(x,y-1)\\
n_d(x,y)&=n_h(x-1,y-1)+ n_v(x-1,y-1)+n_d(x-1,y-1)
\end{align}
for $\ 1\le x,y\le5\ $, and the following initial conditons
\begin{align}
n_h(x,0)&=1, n_v(x,0)=n_d(x,0)=0\ \text{ for }\ 1\le x\le5\ ,\\
n_v(0,y)&=1, n_h(0,y)=n_d(0,y)=0 \ \text{ for }\ 1\le y\le5,\ \text{and}\\
n_v(1,1)&=n_h(1,1)=0, n_d(1,1)=1\ .
\end{align}
Applying these recursions to the initial conditions we get the values of $\ n_h(x,y), n_v(x,y), n_d(x,y)\ $ given in the following table:
\begin{array}{c|cccccc}
{}_y\backslash{}^x&0&1&2&3&4&5\\
\hline
0&&(1,0,0) &(1,0,0) &(1,0,0) &(1,0,0) &(1,0,0)\\
1&(0,1,0) & (0,0,1)&(1,0,1)&(2,0,1)&(3,0,1)&(4,0,1)\\
2 &(0,1,0)&(0,1,1)&(1,1,1)&(2,1,2)&(4,1,3)&(7,1,4)\\
3& (0,1,0) &(0,2,1)&(1,2,2)&(3,3,3)&(6,4,5)&(11,5,8)\\
4 &(0,1,0) &(0,3,1)&(1,4,3)&(4,6,5)&(9,9,9)&(18,13,15)\\
5 &(0,1,0) &(0,4,1)&(1,7,4)&(5,11,8)&(13,18,15)&(28,28,27)
\end{array}
The total numbet of paths from $\ (0,0)\ $ to $\ (5,5)\ $ is therefore $\ n_h(5,5)+n_v(5,5)+n_d(5,5)=$$28+28+27=83\ $.
