Fibonacci-like gap formula

Question

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 code-golf 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)

Answer 1

Pari/GP, 37 bytes

Saved 13 bytes thanks to @xnor.

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

Try it online!

Answer 2

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)

Answer 3

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
           Ʋ - Last 4 links as a monad f(M):
     ÆḊ      -   Determinant of M
       N     -   Negated
         Æṭ  -   Trace of M
        ,    -   Pair; [-det(M), tr(M)]

Answer 4

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.

Answer 5

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.

Answer 6

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.

Try it online or verify all test cases.

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)

Answer 7

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.