MathLabs

Problem 6

Let A and E be opposite vertices of a regular octagon. A frog starts at A and jumps to an adjacent vertex until it reaches E and stops. If a_n counts paths of exactly n jumps ending at E, prove a2n−1=0a_{2n-1}=0 and a2n=(2+2)n−1−(2−2)n−12a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}} for n=1,2,3,…n=1,2,3,\ldots.
Step 4 of 5: Step 4
Previous stepNext step
r2−4r+2=0,r=2±2r^2-4r+2=0,\quad r=2\pm\sqrt2
Detailed analysis

The characteristic equation is r2−4r+2=0r^2-4r+2=0, with roots 2±22\pm\sqrt2, so un=C(2+2)n−1+D(2−2)n−1u_n=C(2+\sqrt2)^{n-1}+D(2-\sqrt2)^{n-1}.