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

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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}$$