# Fibonacci-like gap formula

## Background

The recurrence of the Fibonacci sequence is defined as

$$f(n+2) = f(n+1) + f(n)$$

From this recurrence alone, the following gap formulae (recurrences relating three terms with certain amount of gaps) can be derived:

$$f(n+4) = 3f(n+2) - f(n) \\ f(n+6) = 4f(n+3) + f(n) \\ f(n+8) = 7f(n+4) - f(n)$$

You might have seen the $$\n+6\$$ formula if you have worked on Project Euler #2 hard enough :)

In general, for any $$\a \in \mathbb{Z}^+\$$ (positive integers), there exist unique integer coefficients $$\\alpha, \beta\$$ of the generalized gap formula

$$f(n+2a) = \alpha f(n+a) + \beta f(n)$$

which holds for all $$\n\$$.

We can generalize the Fibonacci recurrence itself too:

$$f'(n+2) = uf'(n+1) + vf'(n)$$

Then it can be shown that, for any $$\a \in \mathbb{Z}^+\$$ and $$\u,v \in \mathbb{Z}\$$, there exists a fully general gap formula with integer coefficients:

$$f'(n+2a) = \alpha f'(n+a) + \beta f'(n) \tag{1}\label{eq1}$$

Note that such a formula is not unique for some values of $$\u, v, a\$$.

## Challenge

Given the values of $$\a, u, v\$$, calculate the pair of values of $$\\alpha\$$ and $$\\beta\$$ in the equation $$\\eqref{eq1}\$$. You don't need to handle cases where the answer is not unique.

All three inputs are guaranteed to be integers. $$\a\$$ is strictly positive.

Standard rules apply. The shortest code in bytes wins.

## Test cases

For u = 1, v = 1
a = 1 -> alpha = 1, beta = 1
a = 2 -> alpha = 3, beta = -1
a = 3 -> alpha = 4, beta = 1
a = 4 -> alpha = 7, beta = -1

For u = -2, v = 3
a = 1 -> alpha = -2, beta = 3
a = 2 -> alpha = 10, beta = -9
a = 3 -> alpha = -26, beta = 27
a = 4 -> alpha = 82, beta = -81

For u = 3, v = -9
a = 1 -> alpha = 3, beta = -9
a = 2 -> alpha = -9, beta = -81
a = 3 -> undefined (not unique)
a = 4 -> alpha = -81, beta = -6561
a = 5 -> alpha = 243, beta = -59049
a = 6 -> undefined (not unique)

• If I did my math right, $\beta$ is $-(-v)^a$, and $\alpha$ is the $a$'th element $f(a)$ of the sequence if we initialize $f(0)=2, f(1)=u$.
– xnor
Oct 28, 2021 at 3:17
• Suggested testcase: $u=3,v=-9,a=6$
– tsh
Oct 28, 2021 at 3:44
• @UnrelatedString Right, it's n. Fixed. Oct 28, 2021 at 5:00
• If $f(0) = x, f(1) = y, f(n + 2) = 3 f(n + 1) - 9 f(n])$, then $f(6) = 729 x, f(12) = 531441 x$. Try it online. There isn't a unique formular between $f(0), f(6), f(12)$. Oct 28, 2021 at 5:55
• @alephalpha Oh, didn't realize that. I changed the challenge to allow solutions like yours (failing when the answer is not unique). Oct 28, 2021 at 6:26

# Pari/GP, 37 bytes

Saved 13 bytes thanks to @xnor.

(u,v,n)->[-(-v)^n,trace([0,1;v,u]^n)]


Try it online!

• I don't know this Pari/GP, but I think it might be shorter to express the output as the trace and the negative determinant of m
– xnor
Oct 28, 2021 at 6:34
• 37 bytes
– xnor
Oct 28, 2021 at 6:37

# Python 3.8 (pre-release), 60 58 bytes

lambda u,v,a:[(p:=u/2-(u*u/4+v)**.5)**a+(u-p)**a,-(-v)**a]


Try it online!

¯2 thanks to @tsh

Originally based on @tsh's answer (now removed due to no complex number support)

# Jelly, 13 12 bytes

Ø.,æ*ÆḊN,ÆṭƲ


Try it online!

Takes input as [v, u] on the left, and a on the right. Outputs as [β, α]

-1 byte thanks to ovs!

Uses xnor's formula that

$$\alpha = \operatorname{tr} \left( \begin{bmatrix} 0 & 1 \\ v & u \end{bmatrix}^a \right) \\ \beta = -(-v)^a = - \det \left( \begin{bmatrix} 0 & 1 \\ v & u \end{bmatrix}^a \right)$$

## How it works

Ø.,æ*ÆḊN,ÆṭƲ - Main link. Takes [v, u] on the left, a on the right
Ø.           - Yield [0, 1]
,          - Pair; [[0, 1], [v, u]]
æ*        - Matrix power to a; Call this M
ÆḊ      -   Determinant of M
N     -   Negated
Æṭ  -   Trace of M
,    -   Pair; [-det(M), tr(M)]

• $(-v)^a$ is the determinant of the matrix (from xnor's comment on the PARI answer), which allows for 12: Ø.,æ*ÆḊN,ÆṭƲ
– ovs
Oct 28, 2021 at 15:43
• @ovs Nice catch, thanks! Oct 28, 2021 at 16:21

# JavaScript (Node.js), 77 bytes

(u,v,a)=>[A=(F=n=>n<2?n^m:u*F(n-1)+v*F(n-2))(a+a,m=0)/F(a),F(a+a,m=1)-A*F(a)]


Try it online!

Let

$$f_1\left(0\right)=0 \\ f_1\left(1\right)=1 \\ f_1\left(n+2\right)=u\cdot f_1\left(n+1\right)+v\cdot f_1\left(n\right)$$

Calculate

$$p=f_1(2a) \\ q=f_1(a)$$

Let

$$f_2\left(0\right)=1 \\ f_2\left(1\right)=0 \\ f_2\left(n+2\right)=u\cdot f_2\left(n+1\right)+v\cdot f_2\left(n\right)$$

Calculate

$$r=f_2(2a) \\ s=f_2(a)$$

We have

$$p=\alpha\cdot q \\ r = \alpha \cdot s + \beta$$

Solve

$$\alpha=\frac{p}{q} \\ \beta=r-\alpha \cdot s$$

Try to undelete this question since all failed testcases currently known had been been excluded from the question. Maybe this one is correct, but I'm not quite sure.

# R, 59 bytes

Or R>=4.1, 52 bytes by replacing the word function with \.

function(u,v,a)c((p=u/2-(u^2/4+v+0i)^.5)^a+(u-p)^a,-(-v)^a)


Try it online!

Based on @xnor's formula and @PyGamer0's answer.

Outputs complex numbers - for pretty integers add 4 bytes for wrapping result in Re.

# 05AB1E, 23 22 bytes

0L‚©IF®øδ*O}Å\O¹θ(Im(‚


Port of @cairdCoinheringaahing's Jelly answer, but without matrix power/multiplication, trace, nor determinant builtins. It uses a slight modification of @xnor's formula:

$$\\alpha = \operatorname{tr} \left( \begin{bmatrix} u&v\\1&0 \end{bmatrix}^a \right) \\ \beta = -(-v)^a\$$

Inputs as [u,v] and a.

Explanation:

0L          # Push [1,0]
‚         # Pair it with the (implicit) input-pair: [[u,v],[1,0]]
©        # Store it in variable ® (without popping)
IG      # Loop the second input a - 1 amount of times:
®     #  Push the matrix from variable ®
ø    #  Zip/transpose it; swapping rows/columns
δ   #  Apply double-vectorized over the two matrices:
*  #   Multiply them together
O #  And then sum each inner-most list
}Å\    # After the loop: pop the matrix and push its main diagonal
O   # Sum it together
¹           # Push the first input-pair again
θ          # Pop and only leave the last item (v)
(         # Negate it
Im       # Take it to the power of the second input a
(      # Negate that again
‚           # Pair the two integers together
# (after which this pair [α,β] is output implicitly as result)


# Charcoal, 38 bytes

ＮθＮη⊞υ²⊞υθＦ⊖Ｎ⊞υ⁺×θ§υ±¹×η§υ±²Ｉ⟦⊟υ±Ｘ±ηＬυ


Try it online! Link is to verbose version of code. Explanation: Uses @xnor's formula.

ＮθＮη


Input u and v.

⊞υ²⊞υθ


Push 2 and u to the predefined empty list.

Ｆ⊖Ｎ⊞υ⁺×θ§υ±¹×η§υ±²


Calculate a-1 more terms so that the last term is now the ath term.

Ｉ⟦⊟υ±Ｘ±ηＬυ


Remove and output the ath term, then calculate the power using the remaining length which is now a.