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?
$\endgroup$ 67 Answers
$\begingroup$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.$$
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 4 $\begingroup$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$
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.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$According to this link* :
$$T_n=1+\frac{(n-1)(2+2(n-2))}{2}$$ Or ,
$\endgroup$$$T_n=1+(n-1)^2$$
