9
$\begingroup$

For $k\ge 2\in\mathbb N$, one can define the $n$-th $k$-nacci number $f_k(n)\ (n=0,1,\cdots)$ as $$f_k(0)=f_k(1)=\cdots=f_{k}(k-2)=0,\ \ f_{k}(k-1)=1,$$$$f_{k}(n+k)=f_{k}(n)+f_k(n+1)+\cdots+f_{k}(n+k-2)+f_{k}(n+k-1)\ \ \ (n=0,1,2,\cdots)$$

Examples :

  • $f_2(n)$ (Fibonacci) : $0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,\cdots$
  • $f_3(n)$ (Tribonacci) : $0,0,1,1,2,4,7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136,5768,\cdots$
  • $f_4(n)$ (Tetranacci) : $0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536,\cdots$

Here is my question. Let us say "$N$ is $k$-nacci" if a number $N$ is a $k$-nacci number.

Question : For $k\ge 3$, how can we fill in the following blank to make the proposition true?

$$\text{A number $N$ is $k$-nacci if and only if $(\ \ \ \ \ \ \ \ \ \ )$.}$$

Any answer is OK as long as one can prove that the proposition is true. Can anyone help?

For $k=2$, we know that the following proposition is true (see here, here):

$$\text{A number $N$ is Fibonacci if and only if either $5N^2-4$ or $5N^2+4$ is a perfect square.}$$

Added : A user Tito Piezas III asked a related question.

$\endgroup$
  • $\begingroup$ A number is $N$ $k$-nacci if and only if (it is $0$, or it is a sum of $k$ successive $k$-nacci numbers) :P. $\endgroup$ – R B Jan 27 '15 at 12:16
  • $\begingroup$ @RB: Thanks:) It is indeed true. $\endgroup$ – mathlove Jan 27 '15 at 12:24
  • $\begingroup$ The proposition for $k=2$ depends on the relationship between the two sequences, the Fibonacci and Lucas numbers, $$L_n^2-5F_n^2=4(-1)^n$$ An analogous proposition may exist for $k=3$ between the tribonacci and sequence A001644 $$F_k = x_1^k+x_2^k+x_3^k = 1, 3, 7, 11, 21, 39, 71, 131,\dots$$ where the $x_i$ are the roots of $x^3-x^2-x-1=0$. $\endgroup$ – Tito Piezas III Jan 27 '15 at 12:27
  • $\begingroup$ @TitoPiezasIII: Thanks. Very interesting. $\endgroup$ – mathlove Jan 27 '15 at 12:37
3
$\begingroup$

Note: Sequences start with $n=0$.

I. $k = 2$

The Lucas numbers,

$$L_n = x_1^n+x_2^n = 2,1,3,4,7,11,18,29,\dots$$

and the Fibonacci numbers,

$$F_n = \frac{x_1^n}{y_1}+\frac{x_2^n}{y_2} = 0,1, 1, 2, 3, 5, 8, 13, 21,\dots$$

where $y_i =2x_i-1$ and the $x_i$ are the roots of $x^2-x-1=0$. Then,

$$x_1^n = \big(\tfrac{1+\sqrt{5}}{2}\big)^n=\tfrac{1}{2}(L_n+F_n\sqrt{5})$$

$$x_2^n = \big(\tfrac{1-\sqrt{5}}{2}\big)^n=\tfrac{1}{2}(L_n-F_n\sqrt{5})$$

Hence,

$$(x_1 x_2)^n = (-1)^n = \tfrac{1}{4}(L_n^2-5F_n^2)$$

II. $k = 3$

(Edited.) Given three sequences with recurrence $s_n = s_{n-1}+s_{n-2}+s_{n-3}$ but different initial values as,

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{Name} & \text{Formula} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & OEIS\\ \hline R_n & x_1^n+x_2^n+x_3^n &3 &1 &3 &7 &11 &21 &39 & 71 & A001644 \\ \hline S_n &\frac{x_1^n}{y_1}+\frac{x_2^n}{y_2}+\frac{x_3^n}{y_3}&3 &2 &5 &10 &17 &32 &59 &108 &(none)\\ \hline T_n &\frac{x_1^n}{z_1}+\frac{x_2^n}{z_2}+\frac{x_3^n}{z_3}&0 &1 &1 &2 &4 &7 &13 &24& A000073 \\ \hline \end{array}$$

$$y_i =\tfrac{1}{19}(x_i^2-7x_i+22)$$ $$z_i =-x_i^2+4x_i-1$$

and the $x_i$ are the roots of $x^3-x^2-x-1=0$, with $T_n$ as the tribonacci numbers and the real root $T = x_1 \approx 1.83929$ the tribonacci constant. Define,

$$a=\tfrac{1}{3}(19+3\sqrt{33})^{1/3},\quad b=\tfrac{1}{3}(19-3\sqrt{33})^{1/3}$$

then we have the nice identity by Pin-Yen Lin,

$$3T^n = R_{n}+(a+b)S_{n-1}+3(a^2+b^2)T_{n-1}$$

and similar expressions for the complex conjugates $x_2^n$ and $x_3^n$ (after correcting some typos in the paper). Hence it is possible to express,

$$(-x_1x_2x_3)^n = (1)^n = \text{in terms of}\; R_{n},\, S_{n-1},\, T_{n-1}$$

analogous to the $k=2$ case, and get rid of irrationalities. For some reason, Lin didn't bring it to this step so we find it with the help of Mathematica. Since $R_n,\;S_n$ can be expressed as sums of $T_m$, define,

$$a,\;b,\;c = T_{n-1},\;T_{n-2},\;T_{n-3}$$

then we get the diophantine cubic Pell-type equation for the tribonacci numbers,

$$a^3 - 2 a^2 b + 2 b^3 - a^2 c - 2 a b c + 2 b^2 c + a c^2 + 2 b c^2 + c^3=1$$

with an infinite number of integer solutions analogous to the Pell equation for the Fibonacci numbers,

$$p^2-5q^2 = \pm 4.$$

III. $k = 4$

Define sequence A073817,

$$U_n = x_1^n+x_2^n+x_3^n+x_4^n = 4, 1, 3, 7, 15, 26, 51, 99, 191,\dots$$

and the tetranacci numbers,

$$V_n = \frac{x_1^n}{y_1}+\frac{x_2^n}{y_2}+\frac{x_3^n}{y_3}+\frac{x_4^n}{y_4} =0,1, 1, 2, 4, 7, 13, 24, 44, 81,149\dots$$

where $y_i =-x_i^3 + 6x_i - 1$ and the $x_i$ are the roots of $x^4-x^3-x^2-x-1=0$. Then,

$$\text{(insert relationship here)}$$

$\endgroup$
  • $\begingroup$ Sorry, mathlove, couldn't find the polynomial relationship. For $k=3$, it might need three sequences, but I'm not sure. I vaguely remember seeing something before... $\endgroup$ – Tito Piezas III Jan 27 '15 at 13:19
  • $\begingroup$ I remember now. There is an identity by Pin-Yen Lin. I've edited my answer. $\endgroup$ – Tito Piezas III Jan 27 '15 at 14:07
  • $\begingroup$ I'm glad to see the interesting relationship though I cannot stop myself from expecting "beautiful" results:) $\endgroup$ – mathlove Jan 27 '15 at 16:49
  • $\begingroup$ @mathlove: I have exactly the same philosophy. P.S. I finally found the polynomial relationship for the tribonacci and its associated sequences. It turned out to be a cubic Pell-type equation. $\endgroup$ – Tito Piezas III Jan 28 '15 at 5:00
  • $\begingroup$ I've never seen such a relationship. The cubic Pell-type equation is very nice but not simple, so my understanding is that it seems difficult to fill in that blank for $k\ge 3$ "beautifully". Anyway, thank you so much! $\endgroup$ – mathlove Jan 28 '15 at 9:46
2
$\begingroup$

A number $N$ is Tribonacci if and only if it can be written as:

$$N= \frac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)}+\frac{\beta^n}{(\beta-\alpha)(\beta-\gamma)}+\frac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}$$

Where $n\geq 1$ and $\alpha, \beta,\gamma$ are the three roots of the polynomial $$x^3-x^2-x-1$$

Source: T. Noe, T. Piezas and E. Weisstein, Tribonacci Number (see here).

$\endgroup$
  • $\begingroup$ Or also,$$T_k=\frac{x_1^k}{-x_1^2+4x_1-1}+\frac{x_2^k}{-x_2^2+4x_2-1}+\frac{x_3^k}{-x_3^2+4x_3-1}$$ where the $x_i$ are the roots of $x^3-x^2-x-1=0$. I remember sending this to Weisstein ages ago. :) $\endgroup$ – Tito Piezas III Jan 27 '15 at 12:32
  • $\begingroup$ Thanks. This is indeed an answer to my question. $\endgroup$ – mathlove Jan 27 '15 at 12:39
  • $\begingroup$ @mathlove: There might be a polynomial relationship between the two sequences. Given me about 30 minutes to expand the answer. :) $\endgroup$ – Tito Piezas III Jan 27 '15 at 12:41
  • $\begingroup$ @TitoPiezasIII: Sure! I would like to see the relationship. $\endgroup$ – mathlove Jan 27 '15 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.