Problem 918: Recursive Sequence Summation
The sequence a n a_n a n is defined by a 1 = 1 a_1=1 a 1 = 1 , and then recursively for n ≥ 1 n\geq1 n ≥ 1 :
a 2 n = 2 a n a 2 n + 1 = a n − 3 a n + 1 \begin{align*}
a_{2n} &=2a_n\\
a_{2n+1} &=a_n-3a_{n+1}
\end{align*} a 2 n a 2 n + 1 = 2 a n = a n − 3 a n + 1 The first ten terms are 1 , 2 , − 5 , 4 , 17 , − 10 , − 17 , 8 , − 47 , 34 1, 2, -5, 4, 17, -10, -17, 8, -47, 34 1 , 2 , − 5 , 4 , 17 , − 10 , − 17 , 8 , − 47 , 34 .
Define S ( N ) = ∑ n = 1 N a n \displaystyle S(N) = \sum_{n=1}^N a_n S ( N ) = n = 1 ∑ N a n . You are given S ( 10 ) = − 13 S(10) = -13 S ( 10 ) = − 13 .
Find S ( 10 12 ) S(10^{12}) S ( 1 0 12 ) .
The goal is to find the sum of the first 10 12 10^{12} 1 0 12 terms of the sequence. A direct computation is impossible, so we need to find a more efficient method by analyzing the structure of the sum S ( N ) S(N) S ( N ) .
Let’s analyze the sum S ( N ) S(N) S ( N ) by splitting it into sums over even and odd indices.
Consider the sum up to an odd number, S ( 2 N + 1 ) S(2N+1) S ( 2 N + 1 ) . By substituting the recurrence relations, we get a telescoping sum:
S ( 2 N + 1 ) = a 1 + ∑ n = 1 N ( a 2 n + a 2 n + 1 ) = a 1 + ∑ n = 1 N ( ( 2 a n ) + ( a n − 3 a n + 1 ) ) = a 1 + 3 ∑ n = 1 N ( a n − a n + 1 ) = a 1 + 3 ( a 1 − a N + 1 ) \begin{align*}
S(2N+1) &= a_1 + \sum_{n=1}^{N} (a_{2n} + a_{2n+1}) \\
&= a_1 + \sum_{n=1}^{N} \big( (2a_n) + (a_n - 3a_{n+1}) \big) \\
&= a_1 + 3 \sum_{n=1}^{N} (a_n - a_{n+1}) \\
&= a_1 + 3(a_1 - a_{N+1})
\end{align*} S ( 2 N + 1 ) = a 1 + n = 1 ∑ N ( a 2 n + a 2 n + 1 ) = a 1 + n = 1 ∑ N ( ( 2 a n ) + ( a n − 3 a n + 1 ) ) = a 1 + 3 n = 1 ∑ N ( a n − a n + 1 ) = a 1 + 3 ( a 1 − a N + 1 )
Since a 1 = 1 a_1=1 a 1 = 1 , we get a simple, powerful formula:
S ( 2 N + 1 ) = 1 + 3 ( 1 − a N + 1 ) = 4 − 3 a N + 1 S(2N+1) = 1 + 3(1 - a_{N+1}) = 4 - 3a_{N+1} S ( 2 N + 1 ) = 1 + 3 ( 1 − a N + 1 ) = 4 − 3 a N + 1
We can easily find the formula for an even number, S ( 2 N ) S(2N) S ( 2 N ) , from this:
S ( 2 N ) = S ( 2 N + 1 ) − a 2 N + 1 = ( 4 − 3 a N + 1 ) − ( a N − 3 a N + 1 ) = 4 − a N \begin{align*}
S(2N) &= S(2N+1) - a_{2N+1} \\
&= (4 - 3a_{N+1}) - (a_N - 3a_{N+1}) \\
&= 4 - a_N
\end{align*} S ( 2 N ) = S ( 2 N + 1 ) − a 2 N + 1 = ( 4 − 3 a N + 1 ) − ( a N − 3 a N + 1 ) = 4 − a N
We need to find S ( 10 12 ) S(10^{12}) S ( 1 0 12 ) . Since 10 12 10^{12} 1 0 12 is an even number, we can use the formula for S ( 2 N ) S(2N) S ( 2 N ) with 2 N = 10 12 2N = 10^{12} 2 N = 1 0 12 , which means N = 5 ⋅ 10 11 N = 5 \cdot 10^{11} N = 5 ⋅ 1 0 11 .
S ( 10 12 ) = 4 − a 5 ⋅ 10 11 S(10^{12}) = 4 - a_{5 \cdot 10^{11}} S ( 1 0 12 ) = 4 − a 5 ⋅ 1 0 11
The problem is now reduced to finding the value of a single term in the sequence, a k a_k a k , for a very large index k = 5 ⋅ 10 11 k = 5 \cdot 10^{11} k = 5 ⋅ 1 0 11 .
The recurrence relations for a n a_n a n depend on the index being even or odd, which suggests a connection to the binary representation of the index. Let’s define a state vector containing two consecutive terms:
v n = ( a n a n + 1 ) v_n = \begin{pmatrix} a_n \\ a_{n+1} \end{pmatrix} v n = ( a n a n + 1 )
We can find a relationship between v k v_k v k and v ⌊ k / 2 ⌋ v_{\lfloor k/2 \rfloor} v ⌊ k /2 ⌋ .
If k = 2 n k=2n k = 2 n (even), then ⌊ k / 2 ⌋ = n \lfloor k/2 \rfloor = n ⌊ k /2 ⌋ = n . The vector v 2 n v_{2n} v 2 n is related to v n v_n v n :
v 2 n = ( a 2 n a 2 n + 1 ) = ( 2 a n a n − 3 a n + 1 ) = ( 2 0 1 − 3 ) ( a n a n + 1 ) = ( 2 0 1 − 3 ) v n \begin{align*}
v_{2n} &= \begin{pmatrix} a_{2n} \\ a_{2n+1} \end{pmatrix} \\
&= \begin{pmatrix} 2a_n \\ a_n - 3a_{n+1} \end{pmatrix} \\
&= \begin{pmatrix} 2 & 0 \\ 1 & -3 \end{pmatrix} \begin{pmatrix} a_n \\ a_{n+1} \end{pmatrix} \\
&= \begin{pmatrix} 2 & 0 \\ 1 & -3 \end{pmatrix} v_n
\end{align*} v 2 n = ( a 2 n a 2 n + 1 ) = ( 2 a n a n − 3 a n + 1 ) = ( 2 1 0 − 3 ) ( a n a n + 1 ) = ( 2 1 0 − 3 ) v n
If k = 2 n + 1 k=2n+1 k = 2 n + 1 (odd), then ⌊ k / 2 ⌋ = n \lfloor k/2 \rfloor = n ⌊ k /2 ⌋ = n . The vector v 2 n + 1 v_{2n+1} v 2 n + 1 is also related to v n v_n v n :
v 2 n + 1 = ( a 2 n + 1 a 2 n + 2 ) = ( a n − 3 a n + 1 2 a n + 1 ) = ( 1 − 3 0 2 ) ( a n a n + 1 ) = ( 1 − 3 0 2 ) v n \begin{align*}
v_{2n+1} &= \begin{pmatrix} a_{2n+1} \\ a_{2n+2} \end{pmatrix} \\
&= \begin{pmatrix} a_n - 3a_{n+1} \\ 2a_{n+1} \end{pmatrix} \\
&= \begin{pmatrix} 1 & -3 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} a_n \\ a_{n+1} \end{pmatrix} \\
&= \begin{pmatrix} 1 & -3 \\ 0 & 2 \end{pmatrix} v_n
\end{align*} v 2 n + 1 = ( a 2 n + 1 a 2 n + 2 ) = ( a n − 3 a n + 1 2 a n + 1 ) = ( 1 0 − 3 2 ) ( a n a n + 1 ) = ( 1 0 − 3 2 ) v n
Let’s define the two transition matrices:
M 0 = ( 2 0 1 − 3 ) M_0 = \begin{pmatrix} 2 & 0 \\ 1 & -3 \end{pmatrix} M 0 = ( 2 1 0 − 3 ) and M 1 = ( 1 − 3 0 2 ) M_1 = \begin{pmatrix} 1 & -3 \\ 0 & 2 \end{pmatrix} M 1 = ( 1 0 − 3 2 )
We now have a single recurrence for the vector v k v_k v k for k ≥ 2 k \ge 2 k ≥ 2 :
v k = M k ( m o d 2 ) ⋅ v ⌊ k / 2 ⌋ v_k = M_{k \pmod 2} \cdot v_{\lfloor k/2 \rfloor} v k = M k ( mod 2 ) ⋅ v ⌊ k /2 ⌋
This means we can find any v n v_n v n by starting with v 1 v_1 v 1 and repeatedly applying the appropriate matrix based on the bits of n n n .
v 1 = ( a 1 a 2 ) = ( 1 2 ) v_1 = \begin{pmatrix} a_1 \\ a_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix} v 1 = ( a 1 a 2 ) = ( 1 2 )
For an index n n n with binary representation ( b m b m − 1 … b 0 ) 2 (b_m b_{m-1} \dots b_0)_2 ( b m b m − 1 … b 0 ) 2 , we can trace the calculation from v 1 v_1 v 1 :
The path from index 1 to index n n n is described by the bits b m − 1 , … , b 0 b_{m-1}, \dots, b_0 b m − 1 , … , b 0 .
For example, to get from v 1 v_1 v 1 to v 3 = v ( 11 ) 2 v_3 = v_{(11)_2} v 3 = v ( 11 ) 2 , we apply M 1 M_1 M 1 . To get to v 5 = v ( 101 ) 2 v_5 = v_{(101)_2} v 5 = v ( 101 ) 2 , we first apply M 0 M_0 M 0 to get v 2 v_2 v 2 , then M 1 M_1 M 1 to get v 5 v_5 v 5 .
The calculation is: v n = M b 0 ( M b 1 ( … ( M b m − 1 v 1 ) … ) ) v_n = M_{b_0} (M_{b_1} (\dots (M_{b_{m-1}} v_1)\dots)) v n = M b 0 ( M b 1 ( … ( M b m − 1 v 1 ) … ))
This allows us to compute v n v_n v n in a number of steps proportional to log 2 ( n ) \log_2(n) log 2 ( n ) , which is very efficient.