Skip to content

Problem 918: Recursive Sequence Summation

Problem 918: Recursive Sequence Summation

The sequence ana_n is defined by a1=1a_1=1, and then recursively for n1n\geq1:

a2n=2ana2n+1=an3an+1\begin{align*} a_{2n} &=2a_n\\ a_{2n+1} &=a_n-3a_{n+1} \end{align*}

The first ten terms are 1,2,5,4,17,10,17,8,47,341, 2, -5, 4, 17, -10, -17, 8, -47, 34.

Define S(N)=n=1Nan\displaystyle S(N) = \sum_{n=1}^N a_n. You are given S(10)=13S(10) = -13.

Find S(1012)S(10^{12}).

The goal is to find the sum of the first 101210^{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).

Let’s analyze the sum S(N)S(N) by splitting it into sums over even and odd indices.

Consider the sum up to an odd number, S(2N+1)S(2N+1). By substituting the recurrence relations, we get a telescoping sum:

S(2N+1)=a1+n=1N(a2n+a2n+1)=a1+n=1N((2an)+(an3an+1))=a1+3n=1N(anan+1)=a1+3(a1aN+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*}

Since a1=1a_1=1, we get a simple, powerful formula:

S(2N+1)=1+3(1aN+1)=43aN+1S(2N+1) = 1 + 3(1 - a_{N+1}) = 4 - 3a_{N+1}

We can easily find the formula for an even number, S(2N)S(2N), from this:

S(2N)=S(2N+1)a2N+1=(43aN+1)(aN3aN+1)=4aN\begin{align*} S(2N) &= S(2N+1) - a_{2N+1} \\ &= (4 - 3a_{N+1}) - (a_N - 3a_{N+1}) \\ &= 4 - a_N \end{align*}

We need to find S(1012)S(10^{12}). Since 101210^{12} is an even number, we can use the formula for S(2N)S(2N) with 2N=10122N = 10^{12}, which means N=51011N = 5 \cdot 10^{11}.

S(1012)=4a51011S(10^{12}) = 4 - a_{5 \cdot 10^{11}}

The problem is now reduced to finding the value of a single term in the sequence, aka_k, for a very large index k=51011k = 5 \cdot 10^{11}.

Part 2: A Matrix Method for finding ana_n

Section titled “Part 2: A Matrix Method for finding ana_nan​”

The recurrence relations for ana_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:

vn=(anan+1)v_n = \begin{pmatrix} a_n \\ a_{n+1} \end{pmatrix}

We can find a relationship between vkv_k and vk/2v_{\lfloor k/2 \rfloor}.

If k=2nk=2n (even), then k/2=n\lfloor k/2 \rfloor = n. The vector v2nv_{2n} is related to vnv_n:

v2n=(a2na2n+1)=(2anan3an+1)=(2013)(anan+1)=(2013)vn\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*}

If k=2n+1k=2n+1 (odd), then k/2=n\lfloor k/2 \rfloor = n. The vector v2n+1v_{2n+1} is also related to vnv_n:

v2n+1=(a2n+1a2n+2)=(an3an+12an+1)=(1302)(anan+1)=(1302)vn\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*}

Let’s define the two transition matrices: M0=(2013)M_0 = \begin{pmatrix} 2 & 0 \\ 1 & -3 \end{pmatrix} and M1=(1302) M_1 = \begin{pmatrix} 1 & -3 \\ 0 & 2 \end{pmatrix}

We now have a single recurrence for the vector vkv_k for k2k \ge 2:

vk=Mk(mod2)vk/2v_k = M_{k \pmod 2} \cdot v_{\lfloor k/2 \rfloor}

This means we can find any vnv_n by starting with v1v_1 and repeatedly applying the appropriate matrix based on the bits of nn.

v1=(a1a2)=(12)v_1 = \begin{pmatrix} a_1 \\ a_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}

For an index nn with binary representation (bmbm1b0)2(b_m b_{m-1} \dots b_0)_2, we can trace the calculation from v1v_1:

  • The path from index 1 to index nn is described by the bits bm1,,b0b_{m-1}, \dots, b_0.
  • For example, to get from v1v_1 to v3=v(11)2v_3 = v_{(11)_2}, we apply M1M_1. To get to v5=v(101)2v_5 = v_{(101)_2}, we first apply M0M_0 to get v2v_2, then M1M_1 to get v5v_5.
  • The calculation is: vn=Mb0(Mb1((Mbm1v1)))v_n = M_{b_0} (M_{b_1} (\dots (M_{b_{m-1}} v_1)\dots))

This allows us to compute vnv_n in a number of steps proportional to log2(n)\log_2(n), which is very efficient.