1 and for n ≥ 2, x(n

Problem 12113

(American Mathematical Monthly, Vol.126, May 2019) Proposed by R. P. Stanley (USA).

Definef (n) and g(n) for n ≥ 0 by

X

n≥0

f (n)xⁿ=X

j≥0

x^2j

j−1

Y

k=0

1 + x^2k+ x^3·2k

and

X

n≥0

g(n)xⁿ=Y

i≥0

1 + x²ⁱ+ x^3·2i .

Find all values ofn for which f (n) = g(n), and find f (n) for these values.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Solution. We have that

F (x) :=X

n≥0

f (n)xⁿ= x + (1 + x + x³) F (x²)

G(x) :=X

n≥0

g(n)xⁿ = (1 + x + x³) G(x²)

and therefore the sequences f (n) and g(n) satisfy the same recurrence relation: x(1) = 1 and for n ≥ 2,

x(n) =

(x(n/2) if n is even,

x(n − 1) + x(n − 3) if n is odd but have different initial conditions, i.e. f (0) = 0 and g(0) = 1.

It follows that f (n) ≤ g(n), and equality holds if and only if n is 1 or it is of the form 2ⁱ(3 · 2^j−1) with i, j ≥ 0. Moreover

f (n) = g(n) =

(1 if n = 1,

Fj+2 if n = 2ⁱ(3 · 2^j−1) with i, j ≥ 0,

where Fk is the k-th Fibonacci number (F0= 0, F1= 1, Fk= Fk−1+ Fk−2 with k ≥ 2).

Indeed, if j = 0 then

f (2ⁱ(3 · 2⁰−1)) = f (2ⁱ⁺¹) = f (1) = 1 = F2. If j = 1 then

f (2ⁱ(3 · 2¹−1)) = f (2ⁱ·5) = f (5) = f (4) + f (2) = 2f (1) = 2 = F3. Finally, for j ≥ 2,

f (2ⁱ·(3 · 2^j−1)) = f (3 · 2^j−1) = f (3 · 2^j−2) + f (3 · 2^j−4)

= f (3 · 2^j−1−1) + f (3 · 2^j−2−1) = Fj+1+ Fj= Fj+2

and we may conclude that the above formula holds by induction.