← Complete problem index

PROJECT EULER · #1007

Alternating Difference

Statement only · UnsolvedOriginal problem ↗

The Fibonacci sequence is defined by F0=0,F1=1 and Fk=Fk−1+Fk−2 for k≥2.

Write down the numbers F0,F1,…,Fn in a row and separate them with n minus signs −.
We want to add n pairs of parentheses () to form a valid expression such that each pair of parentheses contains exactly one minus sign, not counting those contained in its subparentheses.

For example, when n=3, we can form five different expressions in this way:

(((F0−F1)−F2)−F3)=−4((F0−(F1−F2))−F3)=−2((F0−F1)−(F2−F3))=0(F0−((F1−F2)−F3))=2(F0−(F1−(F2−F3)))=−2

The sum of the values of these expressions is equal to −6.

Let A(n) be the sum of the values of all different expressions that can be obtained in this way.
Thus A(3)=−6. Moreover, A(10)=−177666 and A(100)≡71792794mod(109+9).

Find A(107)mod(109+9).

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.