On Sun, Aug 4, 2013 at 3:41 AM, Bill Gosper <billgosper@gmail.com> wrote:
Replacing the Binomials with QBinomials in the Fibonacci identities below, and throwing in a factor of q^k^2, we get the "q-Fibonacci numbers": In[47]:= Expand[FunctionExpand[Table[Sum[q^k^2*QBinomial[n-k,k,q],{k,0,n}],{n,{0,1,2,3,4,5,6,19}}]]] Out[47]= {1,1,1+q,1+q+q^2,1+q+q^2+q^3+q^4,1+q+q^2+q^3+2 q^4+q^5+q^6,1+q+q^2+q^3+2 q^4+2 q^5+2 q^6+q^7+q^8+q^9,1+q+q^2+q^3+2 q^4+2 q^5+3 q^6+3 q^7+4 q^8+5 q^9+6 q^10+7 q^11+9 q^12+10 q^13+12 q^14+14 q^15+17 q^16+19 q^17+23 q^18+25 q^19+29 q^20+32 q^21+37 q^22+40 q^23+46 q^24+50 q^25+56 q^26+61 q^27+68 q^28+73 q^29+81 q^30+86 q^31+94 q^32+100 q^33+108 q^34+113 q^35+122 q^36+127 q^37+135 q^38+140 q^39+148 q^40+152 q^41+160 q^42+163 q^43+169 q^44+172 q^45+177 q^46+177 q^47+182 q^48+181 q^49+183 q^50+181 q^51+182 q^52+178 q^53+178 q^54+172 q^55+170 q^56+164 q^57+160 q^58+152 q^59+148 q^60+139 q^61+133 q^62+124 q^63+118 q^64+108 q^65+102 q^66+92 q^67+85 q^68+76 q^69+70 q^70+61 q^71+56 q^72+48 q^73+43 q^74+36 q^75+32 q^76+26 q^77+23 q^78+18 q^79+15 q^80+12 q^81+10 q^82+7 q^83+6 q^84+4 q^85+3 q^86+2 q^87+2 q^88+q^89+q^90} In[48]:= %/.q->1 Out[48]= {1,1,2,3,5,8,13,6765} (6765 was the console phone # at MIT AI.) These polynomials approach a limit, q-Fibonacci(∞) which is the Rogers-Ramanujan function: In[55]:= Series[1/Product[(1-q^(5*n-4))*(1-q^(5*n-1)),{n,∞}],{q,0,36}] Out[55]= 1+q+q^2+q^3+2 q^4+2 q^5+3 q^6+3 q^7+4 q^8+5 q^9+6 q^10+7 q^11+9 q^12+10 q^13+12 q^14+14 q^15+17 q^16+19 q^17+23 q^18+26 q^19+31 q^20+35 q^21+41 q^22+46 q^23+54 q^24+61 q^25+70 q^26+79 q^27+91 q^28+102 q^29+117 q^30+131 q^31+149 q^32+167 q^33+189 q^34+211 q^35+239 q^36+O[q]^37 (The sum (with its upper limit infinite, with or without reflecting the q-binomial) is not obviously the usual one in the Rogers-Ramanujan identity.) The coefficient sequence A003114 <https://oeis.org/A003114>has a bunch of interesting combinatorial interpretations, enriching the property list of 239 (if you accept its index 36 as somehow fundamental). --rwg
This is apparently the original definition of q-fibonacci, dating back to [9] I. Schur, Gesmmelte Abhandungen, Vol. 2, Springer-Verlag, Berlin, 1973, pp. 117-136 according to http://arxiv.org/pdf/math/0508546v2.pdf .
But just eight years ago, when I could pass Turing's test, I mentioned here an attractive alternative, qfb, to the above, which I called qib. OEIS wisely disinguishes qfb as "Fibonacci polynomial": ----------------------- [Massive headercide] Date: Sun, 11 Sep 2005 01:09:10 -0700 (PDT) From: "R. William Gosper" <rwg@osots.com> Message-Id: <200509110809.j8B89AXH055413@m130.osots.com> To: math-fun@mailman.xmission.com Many of you may remember the spectacularly ill-conditioned "Filbert" matrix pointed out to me by Peter ("Feathers") Groot in the late 60s: E.g., (c89) (genmatrix(lambda([i,j],1/fib(i+j+9)),3),%% = float(%%)) [ 1 1 1 ] [ -- --- --- ] [ 89 144 233 ] [ ] [ 0.01124 0.00694 0.00429 ] [ 1 1 1 ] [ ] (d89) [ --- --- --- ] = [ 0.00694 0.00429 0.00265 ] [ 144 233 377 ] [ ] [ ] [ 0.00429 0.00265 0.00164 ] [ 1 1 1 ] [ --- --- --- ] [ 233 377 610 ] Contrary to appearance, this is good to six figures: (c90) 1/%; [ 89 144 233 ] [ 89.0 144.0 233.0 ] [ ] [ ] (d90) [ 144 233 377 ] = [ 144.0 233.0 377.0 ] [ ] [ ] [ 233 377 610 ] [ 233.0 377.0 610.0 ] But (c91) float(map('invert,d89)) [ 1.0019e+11 2.62304e+11 - 6.86715e+11 ] [ ] (d91) [ 2.62304e+11 6.86691e+11 - 1.79782e+12 ] = [ ] [ - 6.86715e+11 - 1.79782e+12 4.70676e+12 ] [ 5.01351e+7 1.44257e+8 - 3.64668e+8 ] [ ] [ 1.3994e+8 3.67339e+8 - 9.60738e+8 ] [ ] [ - 3.57682e+8 - 9.72036e+8 2.50923e+9 ] The disagreement is even *more* dramatic if the floating numbers on the rhs of d89 are first converted to exact rationals, and the inversion performed exactly! The reason is that the matrix is far closer than 10^-6 to being singular, and truncation to six figures pushes it way over the brink. The true inverse is symmetric and integer. I tried substituting a couple of candidates for q-Fibonaccis to see if inverting made huge q-polynomials. It is tempting to define qib(0):=0, qib(1):=1, n - 2 qib(n) = qib(n - 1) + q qib(n - 2)), for then n 1 floor(- - -) 2 2 ==== 2 \ k qib(n) = > qbn(n - k - 1, k) q / ==== k = 0 where qbn is the q-binomial coefficient (q; q) n qbn(n, k) = -------------------. (q; q) (q; q) k n - k Then, thru qib(11) 0 1 1 1 + q 2 1 + q + q 2 3 4 1 + q + q + q + q 2 3 4 5 6 1 + q + q + q + 2 q + q + q 2 3 4 5 6 7 8 9 1 + q + q + q + 2 q + 2 q + 2 q + q + q + q 4 6 2 3 4 5 6 (1 + q + q ) (1 + q + q + q + q + q + q ) 4 2 3 4 5 6 7 8 9 10 (1 + q ) (1 + q + q + q + q + q + 2 q + 2 q + 2 q + 2 q + q 11 12 + q + q ) 2 3 4 2 3 4 (1 - q + q - q + q ) (1 + q + q + q + q ) 4 5 6 7 8 9 10 11 12 (1 + q + q + q + q + q + q + q + q + q + q ) 2 3 4 5 6 7 8 9 10 1 + q + q + q + 2 q + 2 q + 3 q + 3 q + 4 q + 5 q + 5 q 11 12 13 14 15 16 17 18 + 5 q + 6 q + 6 q + 6 q + 6 q + 6 q + 5 q + 5 q 19 20 21 22 23 24 25 + 4 q + 4 q + 3 q + 2 q + q + q + q and qib(oo) is defined and equal to inf ==== \ A003114(n) 1 > q = ----------------------------------- / oo ==== /===\ n = 0 | | 5 n + 1 5 n + 4 | | (1 - q ) (1 - q ) | | n = 0 oo 2 ==== n \ q = > -------, / (q; q) ==== n n = 0 the famous Rogers-Ramanujan function. But this qib definition produces messy denominators in the Filbert matrix, and worse, fails to distribute over gcd, f(gcd(n,k)) = gcd(f(n),f(k)), unlike f:= vanilla fib. Defining instead qfb[0] := 0, qfb[1] := 1, qfb[n] := qfb[n-1] + q qfb[n-2] (A011973) answers these objections: 0 0 1 1 2 1 3 1 + q 4 1 + 2 q 2 5 1 + 3 q + q 6 (1 + q) (1 + 3 q) 2 3 7 1 + 5 q + 6 q + q 2 8 (1 + 2 q) (1 + 4 q + 2 q ) 2 3 9 (1 + q) (1 + 6 q + 9 q + q ) 2 2 10 (1 + 3 q + q ) (1 + 5 q + 5 q ) 2 3 4 5 11 1 + 9 q + 28 q + 35 q + 15 q + q 2 12 (1 + q) (1 + 2 q) (1 + 3 q) (1 + 4 q + q ) 2 3 4 5 6 13 1 + 11 q + 45 q + 84 q + 70 q + 21 q + q 2 3 2 3 14 (1 + 5 q + 6 q + q ) (1 + 7 q + 14 q + 7 q ) Note that the degree of qfb[n] is floor((n-1)/2), and qfb[2 p] = qfb[p] times a polynomial of equal degree which is 1 mod p. We also have the pleasant addition formula [ qfb qfb ] [ qfb qfb ] [ k + 1 k ] [ 1 0 ] [ n + 1 n ] [ ] . [ ] . [ ] = [ qfb qfb ] [ 0 q ] [ qfb qfb ] [ k k - 1 ] [ n n - 1 ] [ qfb qfb ] [ n + k + 1 n + k ] [ ]. [ qfb qfb ] [ n + k n + k - 1 ] [error in A011973, since corrected, but F(n+1, x) = F(n, x) + x*F(n-1, x)) still has an extra close paren!-] And the q-Filbert inverse contains satisfyingly huge polynomials divided by mere monomial powers of q. (It looks possible to guess the general form, which will probably require q-"superfactorials", i.e. q-extensions of 1^1 2^2 3^3 ... n^n or 1! 2! 3! ... n!.) [...] --rwg PS: 4 2 %i %pi k ==== ---------- \ 1/5 5 > sqrt(8 - 7 %e ) / ==== k = 0 1 1/5 3/5 1 1/5 2/5 2 (------- + 1) 7 (7 + 3) (1 - -------) (7 + 2) 7 sqrt(5) sqrt(5) 2 = ------------------------------- + ----------------------------- + - sqrt(5) sqrt(5) 5 ~ 14.1420530099223 --------------------------- Note that qib(6) is irreducible. I failed to mention that qfb also has a pretty little Binet formula: In[60]:= F[n+1,x]==F[n,x]+x*F[n-1,x]/.F[k_,x]->qfb[k]/.x->q Out[60]= qfb[1+n]==q qfb[-1+n]+qfb[n] In[61]:= RSolve[{%,qfb[0]==0,qfb[1]==1},qfb[n],n] Out[61]= {{qfb[n]->-((2^-n ((1-Sqrt[1+4 q])^n-(1+Sqrt[1+4 q])^n))/Sqrt[1+4 q])}} which A011973 could mention. --rwg WDS>``BUT gravitons cannot be shielded even in principle. When you emit them, they fly away right thru the box walls. Bingo -- you've been measured by an "external environment."'' Then, can gravitons be detected?