Jumpy, Patient Frog Named Sally And A Math Problem About Her Life-V

Let $N(x,y;k)$ denote the number of ways of getting from vertex $x$ to $y$ in $k$ jumps. Then we have the following recursive equations : $N(A,A;k)=N(B,A;k-1)+N(C,A;k-1)\hspace{10pt}(1)$ $N(B,A;k)=N(A,A;k-1)+N(C,A;k-1)\hspace{10pt}(2)$ Due to symmetry of the points $B$ and $C$ , we have $N(B,A;k)=N(C,A;k)=g_k\hspace{20pt}\text{(say)}$ Also, let $N(A,A; k)=f_k$ . Then equations (1) and (2) are simplified as $f_k=2g_{k-1}, \hspace{10pt}(3)$ $g_k=f_{k-1}+g_{k-1}\hspace{10pt}(4)$ Eliminating $f_k$ from Eqns (3) and (4), we have $g_k=g_{k-1}+2g_{k-2}$ with the initial conditions $g_1=1,g_2=1$ . Solving the above linear recurrence for $g_k$ , we have $g_k=\frac{1}{3}\big(2^{k}-(-1)^k\big)$ And hence $f_k=\frac{2}{3}\big(2^{k-1}-(-1)^{k-1}\big)$ The above is an exact solution for $k$ jumps. For large $k$ , the above may be simplified as $f_k\approx \frac{1}{3}2^{k}$ Hence for $k=132435$ , the answer follows (after taking logarithm to the base of $10$ and then exponentiating the result).