0

I am using Narayana’s cows sequence OEIS A000930 in a paper I am about to submit to a conference. The link gives a closed form, however, I am not sure if I can cite the link in the paper because some program committee members will (most likely) complain about it.

The sequence is $g(n) = g(n-3) + g(n-1)$, where $g(0)=g(1)=g(2)=1$. The link says that $g(n)=\left\lfloor dc^n+\frac12\right\rfloor$, where $d \approx 0.611$ and $c\approx 1.466$.

I was wondering if there is a paper that contains/proves this closed form formula. (I looked through several papers but I was not able to find it.)

Koko Nanahji
  • 13
  • 1
    Citing OEIS is common practice. Why do you think this would not be acceptable? There are references in the OEIS page you link to where the formula may be proved. – Pedro Nov 22 '21 at 22:22
  • 1
    If you are looking at a(n) = floor(d*c^n + 1/2) where c is the real root of x^3-x^2-1 and d is the real root of 31*x^3-31*x^2+9*x-1 (c = 1.465571... = A092526 and d = 0.611491991950812...). - Benoit Cloitre, Nov 30 2002 then you can certainly reference OEIS and mention his name (he is a serious researcher) – Henry Nov 22 '21 at 22:27
  • Thank you for quick reply. I was under the impression that the cited material are supposed to be from peer reviewed resources. I will try to add it, and see if they complain or not. – Koko Nanahji Nov 22 '21 at 22:28

2 Answers2

2

ADDED next morning: took forever, I finally confirmed that my $A$ satisfies $31A^4 - 22 A^2 + 8A - 1$ which reduces, eventually $$ 31 A^3 - 31 A^2 + 9A - 1 = 0$$ Meanwhile, the dependence is $A = \frac{\alpha^3}{\alpha^3 + 2}$ with $$ \alpha \approx 1.465571231876768026656731225 $$ $$ A \approx 0.6114919919508125184143170109 $$ An intermediate step was confirming that $\alpha^{12}-3\alpha^9 - \alpha^6 + 2 \alpha^3 - 1=0.$ From

$$ x^{12} - 3 x^9 - x^6 + 2 x^3 - 1 = $$ $$ (x+1)(x^2-x+1)(x^3-x^2-1)(x^6+x^5+x^4-2x^3-x^2+1) $$

Then using $\alpha^3 = \frac{2A}{1-A}$ That is, $\delta = \alpha^3$ is a root of $\delta^4 - 3 \delta^3 - \delta^2 + 2 \delta - 1 = (\delta+1)(\delta^3-4\delta^2 + 3 \delta -1) $

ORIGINAL:the set of sequences $x_n$ with $ x_{n+3} - x_{n+2} - x_n = 0$ is a vector space over the complexes. A basis is $$ \alpha^n \; \; , \; \; \beta^n \; \; , \; \; \bar{\beta}^n \; \; , \; \; $$ where $ \alpha \approx 1.465571231876768026656731225 $ and $ \beta \approx -0.2327856159383840133283656126 + 0.7925519925154478483258983007i$

Note that $\beta$ and $\bar{\beta}$ have norm smaller than $1,$ so that $\beta^n$ and $\bar{\beta}^n$ approach $0$ fairly quickly.

I see, you are calling my $\alpha = C$

Any complex series can be written using the basis. If all elements of the sequence are real, the coefficients come out $$ x_n = A \alpha^n + B \beta^n + \bar{B} \bar{\beta}^n $$

Once more, you have my $A = d.$ From the comment about the norms going to zero, we know that ( because your sequence is always integers) $x_n$ really is the closest integer to $A \alpha^n.$ Rounding a positive real $t$ to the nearest integer can be done with $ \left\lfloor t + \frac{1}{2} \right\rfloor $

Will Jagy
  • 139,541
  • Thanks for the explanation. Can you please explain how to find $A$ as well. I know that it is the real root of $31\cdot x^3-31\cdot x^2+9\cdot x-1$ but I am not sure how to derive that. – Koko Nanahji Nov 23 '21 at 01:20
  • In the paper by Xin Lin (https://www.researchgate.net/publication/348652924_On_the_Recurrence_Properties_of_Narayana%27s_Cows_Sequence), they say $A= \frac{\alpha^2}{\alpha^3+2}=0.417\dots$ but this does not match the answer that I found at other places which is $A\approx 0.61$. – Koko Nanahji Nov 23 '21 at 01:25
  • @KokoNanahji Lin's $A,B,C$ must be a little different because he says $G_0 = 0$ then $G_1=G_2=G_3 = 1$ You have $g_0=g_1=g_2 =1$ and I guess $g_{-1} = 0$ Lin would get your desired numbers if the formulas just after (4) were changed to $A+B+C=1$ – Will Jagy Nov 23 '21 at 02:13
  • @KokoNanahji correcting Lin gives $A= \frac{\alpha^3}{\alpha^3 + 2} = \alpha \cdot \frac{\alpha^2}{\alpha^3 + 2}$ – Will Jagy Nov 23 '21 at 02:54
  • Sounds good. Thank you very much. – Koko Nanahji Nov 23 '21 at 03:46
0

Just in case you want the exact formulae

$$c_1=\frac{1}{3} \left(1+2 \cosh \left(\frac{1}{3} \cosh ^{-1}\left(\frac{29}{2}\right)\right)\right)$$

and

$$d_1=\frac 13 \Bigg[1+\frac{4}{\sqrt{31}}\cosh \left(\frac{1}{3} \cosh ^{-1}\left(\frac{\sqrt{31}}{2}\right)\right) \Bigg]$$

Claude Leibovici
  • 260,315