Calculating (3 + sqrt(5))^n exactly

Octave, 26 bytes

[3 5;1 3]**input('')*[1;0]

Because (a+b*sqrt(5)) * (3+sqrt(5)) = (3a+5b) + (a+3b) * sqrt(5),

multiplying input vector

| 1 |    /* a = 1 */
| 0 |    /* b = 0 */

which stands for 1 = (3+sqrt(5))^0 by matrix

| 3 5 |
| 1 3 |

seems natural. Instead of looping n times, we rather raise the matrix to the power of n and then multiply it by input vector.


Python 2, 50

a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b

Multiplies by 3+sqrt(5) repeatedly by its action on the pair (a,b) representing a+b*sqrt(5). Equivalent to starting with the column vector [1,0] and left-multiplying n times by the matrix [[3,5],[1,3]].


Julia, 22 20 bytes

n->[3 5;1 3]^n*[1;0]

This creates a lambda function which takes a single integer as input and returns a 2-element vector of integers corresponding to the solution [a, b]. To call it, give it a name, e.g. f=n->....

Start by multiplying

Initial expand

We can then translate the right hand side of this equation into a 2-column matrix, where the first corresponds to the coefficient of a and the second to the coefficient of b:

Matrix

Multiply this matrix by itself n times, then right multiply by the column vector (1, 0), and POOF! Out pops the solution vector.

Examples:

julia> println(f(0))
[1,0]

julia> println(f(5))
[1968,880]