If $a = \frac{1+\sqrt5}2$, then what is $a^{18} + \frac{323}{a^6}$? My question is this:

If $a = \frac{1+\sqrt5}2,\frac{1-\sqrt5}2$, then what is $a^{18} + \frac{323}{a^6}$?

It is an AMC style question and is timed, so I will not be able to use solutions with a lot of case work.
I defined $a$ from part a of a 2 part question and would like to know how to do this without the use of a calculator.
 A: Okay, actually we can do better than what I suggested in the comments. The basic move is to repeatedly use the identity $a^2 = a + 1$ together with binary exponentiation. We have
$$a^3 = a(a^2) = a(a + 1) = a^2 + a = 2a + 1$$
$$a^6 = (a^3)^2 = (2a + 1)^2 = 4a^2 + 4a + 1 = 8a + 5$$
$$a^{12} = (a^6)^2 = (8a + 5)^2 = 64a^2 + 80a + 25 = 144a + 89$$
$$a^{18} = a^6 \cdot a^{12} = (8a + 5)(144a + 89) = 1152a^2 + 1432a + 445 = 2584a + 1597$$
which tells us the first term. To evaluate the second term it's convenient to work as follows. Introduce $b = \frac{1 - \sqrt{5}}{2}$, the conjugate of $a$, which satisfies $ab = -1$ and $a + b = 1$. We have $\frac{323}{a^6} = 323b^6$, and $b$ also satisfies $b^2 = b + 1$, so exactly the same computation as before applies and we get $b^6 = 8b + 5 = 13 - 8a$. Altogether this gives
$$a^{18} + \frac{323}{a^6} = (2584a + 1597) + 323(13 - 8a) = \boxed{5796}$$
if I haven't made any arithmetic errors.

Some discussion. In general we can prove by induction that
$$a^n = F_n a + F_{n-1}$$
where $F_n$ are the Fibonacci numbers. Binary exponentiation applied to $a$ then proves a doubling identity for the Fibonacci numbers allowing them to be calculated quickly in the same way that binary exponentiation allows powers to be calculated quickly. Specifically we get
$$a^{2n} = F_{2n} a + F_{2n-1} = (F_n a + F_{n-1})^2 = F_n^2 a^2 + 2 F_n F_{n-1} a + F_{n-1}^2 = (F_n^2 + 2 F_n F_{n-1}) a + (F_n^2 + F_{n-1}^2)$$
which gives the pair of doubling identities
$$F_{2n} = F_n(F_n + 2F_{n-1}) = F_n(F_n + F_{n+1})$$
$$F_{2n-1} = F_n^2 + F_{n-1}^2.$$
This isn't a special feature of $a$ and similar identities can be proven for any quadratic irrational. Abstractly we're repeatedly using the fact that the corresponding quadratic field has basis $\{ 1, a \}$ as a vector space.
The exact same proof conjugated gives that $b^n = F_n b + F_{n-1}$ and subtracting these two identities from each other gives $a^n - b^n = (a - b) F_n$, or slightly rearranging, Binet's formula
$$F_n = \frac{a^n - b^n}{a - b}.$$
There's a more general story to tell here about any sequence defined by a linear recurrence relation; I don't know a good self-contained reference off the top of my head unfortunately.
A: In this particular case, it may be useful to notice that
$\phi = \frac12(1 + \sqrt5)$ is the Golden Ratio,
which satisfies the equation
$$ \phi^2 = \phi + 1. $$
It follows immediately that $\phi^2 = \frac12(3+\sqrt5).$
Further, $\phi^3 = \phi^2 + \phi = 2 + \sqrt5,$
$\phi^4 = \phi^3 + \phi^2 = \frac12(7+3\sqrt5),$ etc.
Also, $\phi^{-1} = \phi - 1 =  \frac12(-1 + \sqrt5),$
$\phi^{-2} = 1 - \phi^{-1} = \frac12(3 - \sqrt5),$ etc.
You could go to any power of $\phi$ this way, although you can also get $\phi^6$ by squaring $\phi^3$ and $\phi^{18}$ by cubing $\phi^6$
(using the binomial theorem).
A: We have $a^n=F_n a + F_{n-1}$, where $F_n$ is the $n$th Fibonacci number. This is easily proved by induction since $a^2=a+1$. This also holds for $b=-1/a$: $b^n=F_n b + F_{n-1}$.
Therefore,
$$
a^{18} + \frac{323}{a^6}
= a^{18} + 323b^6
= F_{18} a + F_{17} + 323 (F_6 b + F_5)
= 2584 a + 1597 + 323(8b+5)
\\= 2584 a + 2584 b + 3212 
= 2584 (a+b) + 3212
= 2584 + 3212
= 5796
$$
since $a+b=1$.
Alternatively, use polynomial division to find the remainder of $a^{18} + 323(1-a)^6$ modulo $a^2-a-1$. This is systematic but not pretty to do by hand. WA helps.
A: 
Lemma.  Define $$L_n = a^n + (-a)^{-n}.$$  Then $L_n$ is a Lucas number satisfying the recurrence $$L_{n+1} = L_n + L_{n-1}, \\ L_0 = 2, \quad L_1 = 1.$$
Proof.  Since $a^2 = a + 1$, or equivalently, $$a - a^{-1} = 1,$$ we have $$(a^n + (-a)^{-n})(a - a^{-1}) = a^{n+1} + (-a)^{-(n+1)} - \left(a^{n-1} + (-a)^{-(n+1)}\right),$$ hence $$L_n L_1 = L_{n+1} - L_{n-1}.$$
Along with $L_0 = a^0 + (-a)^0 = 2$, this proves the claim.

We next use this recursion to compute the table
$$\begin{array}{c|ccccccccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
\hline
L_n & 2 & 1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 & 76 & 123 & 199 & 322 
\end{array}$$
Therefore
$$\begin{align}
a^{18} + 323 a^{-6} 
&= a^6 (a^{12} + 323a^{-12}) \\
&= a^6(a^{12} + a^{-12} + 322a^{-12}) \\
&= a^6 (L_{12} + 322 a^{-12}) \\
&= a^6 (322 + 322 a^{-12}) \\
&= 322 (a^6 + a^{-6}) \\
&= 322 L_6 \\
&= 322 (18) \\
&= 5796.
\end{align}$$
