Find the $n$th term of $1, 2, 5, 10, 13, 26, 29, …$

How would you find the $n$th term of a sequence like this?

$1, 2, 5, 10, 13, 26, 29, …$

I see the sequence has a group of three terms it repeats: Double first term to get second term, add three to get third term, repeat.

What about: $2, 3, 6, 7, 14, 15, 30,… $?

Again the sequence has a group of three terms it repeats: Add one to first term to get second term, then double second term to get third term.

How do you compute the $n$th term of such sequences directly, without iterating through all preceding terms?

Solutions Collecting From Web of "Find the $n$th term of $1, 2, 5, 10, 13, 26, 29, …$"

For the first sequence:

$$S_n = {2}^{(2+\lfloor\frac{n}{2}\rfloor)}+6(\frac{n}{2}-\lfloor\frac{n}{2}\rfloor-1)$$

For example:

  • $S_1 = 2^2-3 = 1$
  • $S_2 = 2^3-6 = 2$
  • $S_3 = 2^3-3 = 5$
  • $S_4 = 2^4-6 = 10$
  • $S_5 = 2^4-3 = 13$
  • $S_6 = 2^5-6 = 26$
  • $S_7 = 2^5-3 = 29$

For the second sequence:

$$S_n = {2}^{\lceil\frac{n}{2}\rceil}+2(\frac{n}{2}-\lfloor\frac{n}{2}\rfloor-1)$$

For example:

  • $S_1 = 2^2-2 = 2$
  • $S_2 = 2^2-1 = 3$
  • $S_3 = 2^3-2 = 6$
  • $S_4 = 2^3-1 = 7$
  • $S_5 = 2^4-2 = 14$
  • $S_6 = 2^4-1 = 15$
  • $S_7 = 2^5-2 = 30$

For example, consider the 1st sequence. One can write two recurrence relations,
$$F_{2k}=2F_{2k-1},\qquad F_{2k+1}=F_{2k}+3,$$
and use them to deduce a relation involving only odd terms:
$$F_{2k+1}=2F_{2k-1}+3.$$
The general solution of this is
$$F_{2k+1}=\alpha\cdot 2^k-3,$$
and the value of the constant $\alpha=2$ is fixed by $F_1=1$. Hence
$$F_{2k+1}=2^{k+2}-3,\qquad F_{2k}=2^{k+2}-6.$$

Denote the $n$-th term by $x_{n}$ and have a look at the terms with
odd index $n$. Based on what you remarked yourself:

$x_{1}=1$

$x_{3}=2x_{1}+3=2+3$

$x_{5}=2x_{3}+3=2\left(2+3\right)+3=2^{2}+2.3+3$

$x_{7}=2x_{5}+3=2\left(2^{2}+2.3+3\right)+3=2^{3}+2^{2}.3+2.3+3$

et cetera.

This starts to look like

$x_{2n+1}=2^{n}+\left(2^{n-1}+2^{n-2}+\cdots+1\right)3=2^{n}+\left(2^{n}-1\right)3=2^{n+2}-3$

This can be proved by induction and its easy now to find that $x_{2n}=x_{2n+1}-3=2^{n+2}-6$.

On a sortlike way you come to $y_{2n+1}=2^{n+2}-2$ and $y_{2n}=2^{n+1}-1$ where $y_{n}$
denotes the $n$-th term of the second sequence.

A more general approach to solving for the $n$th term of such sequences uses matrix multiplication. Suppose the even terms are nonzero constant $r\neq 1$ times the preceding odd terms, while the odd terms are constant $d$ plus the preceding even terms. We have:

$$ \begin{pmatrix} 1 & 0 & d \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}
\begin{pmatrix} a_{2n} \\ a_{2n-1} \\ 1 \end{pmatrix} =
\begin{pmatrix} a_{2n+1} \\ a_{2n} \\ 1 \end{pmatrix} $$

$$ \begin{pmatrix} r & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}
\begin{pmatrix} a_{2n+1} \\ a_{2n} \\ 1 \end{pmatrix} =
\begin{pmatrix} a_{2n+2} \\ a_{2n+1} \\ 1 \end{pmatrix} $$

Combining these by matrix multiplication gives the double step:

$$ \begin{pmatrix} r & 0 & rd \\ 1 & 0 & d \\ 0 & 0 & 1 \end{pmatrix}
\begin{pmatrix} a_{2n} \\ a_{2n-1} \\ 1 \end{pmatrix} =
\begin{pmatrix} a_{2n+2} \\ a_{2n+1} \\ 1 \end{pmatrix} $$

The problem is then reduced to finding a closed form for natural powers of the matrix:

$$ A = \begin{pmatrix} r & 0 & rd \\ 1 & 0 & d \\ 0 & 0 & 1 \end{pmatrix} $$

which can be done by diagonalization, since $A$ has three distinct eigenvalues $0,1,r$.

Represent $A$ with respect to the corresponding basis of eigenvectors:

$$ \left\{ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix},
\begin{pmatrix} -rd \\ – d \\ r-1 \end{pmatrix},
\begin{pmatrix} r \\ 1 \\ 0 \end{pmatrix} \right\} $$

and the resulting similarity transformation diagonalizes $A$, say $A = S D S^{-1}$ where $D= \operatorname{diag}(0,1,r)$. Thus, assuming an initial value $a_1$ and $a_2 = ra_1$:

$$ A^n \begin{pmatrix} a_2 \\ a_1 \\ 1 \end{pmatrix} =
S D^n S^{-1} \begin{pmatrix} ra_1 \\ a_1 \\ 1 \end{pmatrix} =
\begin{pmatrix} a_{2n+2} \\ a_{2n+1} \\ 1 \end{pmatrix} $$

The powers of $D$ are explicitly $D^n = \operatorname{diag}(0,1,r^n)$, so this gives a direct expression for any terms in the sequence starting from $a_1$:

$$ a_{2n+1} = r^n a_1 + \frac{r^n -1}{r-1} d $$

$$ a_{2n+2} = r a_{2n+1} = r^{n+1} a_1 + \frac{r^n -1}{r-1} rd $$

taking advantage of the calculation DanielV carried out in the Comment below.

This matrix multiplication technique can be modified to handle more general mixtures of arithmetic and geometric rules.

Look at the alternate terms of your sequence: These are: 1,5,13,29,… and the other terms are exactly twice the previous terms: 2,10,26,… . Now, consider the sequence: 1,5,13,29. Their successive differences are: 5-1=4, 13-5=8,29-13=16, and so on. So, the next alternate term after 29 is 29+32=61. So, the nth alternate term is : 1+2^2+2^3+…+2^n = 2^(n+1) – 3, i.e. the (2n-1)th term of your sequence is 2^(n+1) – 3, and the (2n)th term is twice the (2n-1)th term, which is 2^(n+2)-6.

One approach is to map $n$ to a pair of coordinates $(i,j)$ where $i$ denotes the group and $j$ the element of the $i$-th group.

For example, here I generalise the second sequence you give:

\begin{align}
&u_0 \\
& u_1=u_0+\alpha \\
& u_2=u_1+\alpha \\
& … \\
& u_{m-1}=u_{m-2}+\alpha \\
& u_m=\beta u_{m-1} \\
& u_{m+1}=u_{m} + \alpha \\
& …
\end{align}

Note that

$$ u_{im+j} = \beta^iu_0+(m-1)\alpha\sum_{k=1}^i\beta^k + j\alpha $$

Then you can make use of floor and modulo functions to map $n\mapsto(i,j)$:

\begin{align}
i&=\lfloor n/m\rfloor \\
j&=\mathrm{mod}(n,m)
\end{align}


Note that this approach works for more complicated sequences where the recurrence approach fails.