[seqfan] Re: Two tenuously related problems concerning squares

[William Keith]

On Sun, Jun 16, 2013 at 11:04 AM, Alonso Del Arte
<alonso.delarte at gmail.com>wrote:

> 1. Is it always possible to express n^2 as a sum of n distinct Fibonacci
> numbers, or at least almost so but allowing two 1s? e.g.,
>
>  1 = 1
>  4 = 1 + 3
>  9 = 1 + 3 + 5
> 16 = 1 + 2 + 5 + 8
> 25 = 1 + 1 + 2 + 8 + 13
>

No. It can't be done with 8 Fibonacci numbers for n^2 = 64.  Or apparently
any higher square; at least certainly not up to 10,000, according to a
quick Mathematica search.

In[1] := FibSeries = Expand[Product[1 + z q^Fibonacci[n], {n, 1, 21}]];

In[2] := Sum[(z^n) (q^(n^2))*
  Coefficient[Coefficient[FibSeries, q^(n^2)], z^n], {n, 1, 100}]

Out[2] := 2 q z + 2 q^4 z^2 + 2 q^9 z^3 + 2 q^16 z^4 + q^25 z^5 + q^36 z^6
+
 q^49 z^7

In[3] := Coefficient[FibSeries, q^(64)]

Out[3] := 2 z^3 + 4 z^4 + 3 z^5 + 3 z^6 + z^7

There may be a proof with Binet's formula.

William Keith