Detailed mathematical approach

Problem Summary

Place \(F_0,F_1,\ldots,F_n\) in order with a minus sign between adjacent terms. A valid expression is a full parenthesization: every one of the \(n\) pairs of parentheses encloses exactly one top-level minus sign, although either side may contain further parenthesized subexpressions. The task is to add the values of all syntactically different expressions.

There are \(C_n\) such expressions, where \(C_n\) is the \(n\)-th Catalan number. Direct construction is therefore impossible at \(n=10^7\). We need

$$A(10^7)\pmod{p},\qquad p=10^9+9,$$

with the published checks \(A(3)=-6\), \(A(10)=-177666\), and \(A(100)\equiv71792794\pmod p\).

Mathematical Approach

Parenthesizations are ordered full binary trees

A parenthesized subtraction expression with \(m=n+1\) operands is an ordered full binary tree with \(m\) leaves. Its root chooses a unique split after \(k\) leaves: the left subtree uses the first \(k\) operands and the right subtree uses the remaining \(m-k\). A block of \(j+1\) leaves has

$$C_j=\frac{1}{j+1}\binom{2j}{j}$$

possible trees. The root split is the key because the value of the whole tree is “left value minus right value,” and every valid tree occurs at exactly one split.

A geometric probe records every leaf coefficient at once

Temporarily replace the Fibonacci operands by \(1,t,t^2,\ldots,t^{m-1}\). Let \(P_m(t)\) be the sum of the values of all parenthesizations of these \(m\) formal operands. In particular, \(P_1(t)=1\).

For a split after \(k\) leaves, the left sum \(P_k(t)\) is repeated once for every right tree, while the right sum is repeated once for every left tree and is shifted by \(t^k\). Therefore

$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$

This recurrence does not merely count trees. It preserves the complete signed contribution of every leaf position. For example,

$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$

Worked sign-polynomial example: \(n=3\)

For four leaves, adding the five tree polynomials gives

$$P_4(t)=5-5t+t^2-t^3.$$

In the Fibonacci ring, \(r^2=1+r\) and \(r^3=1+2r\). Hence the root coefficient is

$$[r]P_4(r)=-5+1-2=-6,$$

which is the sum \(-4-2+0+2-2=-6\) from the five displayed expressions in the problem. This example simultaneously checks the Catalan multiplicities, the right-subtree sign, the exponent shift, and the Fibonacci extraction rule.

Collapse the Catalan convolution with generating functions

Introduce

$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$

Thus \(T(z)\) is simply the ordinary Catalan generating function (also often denoted \(C(z)\)), while \(P(z,t)\), equivalently \(P(z,x)\) when the marker is named \(x\), is the bivariate sign-polynomial series.

Summing the root-split recurrence over \(m\) turns the two convolutions into products:

$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$

Writing \(q(z)=\sqrt{1-4z}\) and \(s(z)=\sqrt{1-4tz}\), we obtain the compact algebraic function

$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$

Thus the exponentially large family of trees has been compressed into coefficient extraction from one algebraic power series.

Fibonacci numbers are one coefficient in a quadratic ring

Work modulo \(p\) in the quotient ring

$$R=\mathbb{F}_p[r]/(r^2-r-1).$$

Every element has the form \(a+br\). The defining relation gives, for \(i\ge1\),

$$r^i=F_{i-1}+F_ir,$$

and \(r^0=1\) has \(r\)-coefficient \(0=F_0\). Consequently the coefficient of \(r\) in \(P_m(r)\) is exactly the sum obtained when leaf \(i\) receives \(F_i\):

$$A(n)=[r]\,P_{n+1}(r).$$

No square root of \(5\) and no extension-field inversion is needed. Addition, subtraction, and multiplication by \(r\), \(r+1\), \(r-1\), or \(2-r\) reduce to operations on the pair \((a,b)\):

$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$

Rationalization gives a constant-memory coefficient recurrence

Now set \(t=r\), \(q(z)=\sqrt{1-4z}\), and \(s(z)=\sqrt{1-4rz}\). Define

$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$

Using \(q(z)^2=1-4z\), \(s(z)^2=1-4rz\), and \(r^2=r+1\), rationalizing the denominator of \(P\) yields

$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$

This identity is chosen because its denominator is only linear in \(z\). It lets the implementation advance one coefficient at a time instead of storing a power-series table.

Factorial scaling removes divisions inside the loop

Let the factorial-scaled coefficients be

$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$

With \(a_0=b_0=c_0=1\), \(c_{-1}=0\), and \(u_0=0\), coefficient comparison gives

$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$

The scaled coefficient of \(N(z)\) is

$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$

and the rationalized identity becomes the one-step update

$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$

The loop runs through \(m=n+1\). Finally it undoes the factorial scaling and extracts the root component:

$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$

Because \(p\) is prime and \(n+1=10000001\lt p\), both \(4\) and \((n+1)!\) are nonzero modulo \(p\). Their inverses are computed with Fermat's little theorem, \(x^{-1}\equiv x^{p-2}\pmod p\).

Why the small brute-force check is valuable

The optimized recurrence is compact but algebraically dense. For \(0\le n\le10\), the implementations independently enumerate every root split, construct every parenthesized value, and compare its direct sum with the ring recurrence. They also check the three published values. This catches sign errors at a right subtree, incorrect index shifts, and mistakes in either ring component before the large instance is evaluated.

Correctness Argument

Lemma 1. The recurrence for \(P_m(t)\) sums every valid parenthesization exactly once. Every full binary tree has one root split \(k\); the Catalan factors count the choices for the opposite subtree, and the right block acquires exactly the shift \(t^k\) and the root minus sign.

Lemma 2. The generating function \(P(z,t)\) has coefficient \(P_m(t)\). Multiplying by \(zC(z)\) and \(tzC(tz)\) reproduces the two split convolutions of Lemma 1, so solving the resulting linear equation gives \(2z/(2+q-s)\).

Lemma 3. In \(R\), the \(r\)-coefficient of \(r^i\) is \(F_i\). Linearity therefore changes the formal leaf weights \(t^i\) in \(P_m(t)\) into the required Fibonacci weights when \(t=r\).

Lemma 4. The updates for \(a_m,b_m,c_m,d_m,u_m\) are coefficient identities of the square-root series and the rationalized equation. Factorial scaling is reversible because the relevant factorial is invertible modulo \(p\).

By Lemmas 1 and 2, \(P_{n+1}\) represents the sum over all valid expressions; by Lemma 3 its root component is \(A(n)\); and by Lemma 4 the loop computes precisely that component. Hence the printed residue is \(A(10^7)\bmod(10^9+9)\).

How the Code Works

alternating_sum keeps only the current \(a_m\), \(b_m\), the last two \(c_m\) values, the previous \(u_m\), and the running factorial. A ring element is stored as its constant and root components. The four short multiplication identities above are expanded directly in Python and Java to avoid allocating millions of temporary objects; they are the same operations performed by the C++ RingElement helpers.

mod_pow performs binary exponentiation for the two modular inverses. brute_values is deliberately separate from the optimized derivation: it recursively realizes all root splits for small inputs. run_checkpoints compares both methods for \(n=0,\ldots,10\), then verifies the published residues.

Complexity Analysis

The main recurrence performs a constant number of modular ring operations for each \(m=1,\ldots,n+1\), so it takes \(O(n+\log p)\) time. The exponentiation term is negligible beside \(n=10^7\). Only a fixed number of scalar residues is retained, giving \(O(1)\) auxiliary memory.

Direct enumeration would require \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) expressions and is exponentially impossible. Even storing all coefficients through degree \(n\) would use \(O(n)\) memory; the linear-denominator recurrence avoids that storage.

Footnotes and References

1. Problem page: Project Euler 1007 - Alternating Difference
2. Catalan numbers: Wikipedia - Catalan number
3. Generating functions: Wikipedia - Generating function
4. Fibonacci sequence: Wikipedia - Fibonacci sequence
5. Quotient rings: Wikipedia - Quotient ring
6. Fermat's little theorem: Wikipedia - Fermat's little theorem