Finding the nth term of 1, 6, 24, 76,212,....

Question

What different methods of recursion can I use to find the nth term of this recursion? This should be simple but I don't know what I'm missing. Could you demonstrate the method?

$n(0)= 1$, $n(1)= 6$, $n(2)= 24$, $n(3)= 76$, $n(4)= 212$ $...$

$Recurrence: $

$$w_0 = 1$$ $$\forall n \in \mathbb{N}, w_{n+1} = w_n +4 $$ $$ z_0 = w_0$$ $$\forall n \in \mathbb{N}, z_{n+1} = z_n + (w_{n+1}) 2^n$$

$$z_0 = w_0 = 1$$ $$z_1 = z_{0+1} = z_0 + (w_0+_1)2^0 = 1 + ((1+(1)4)2^0 = 6$$ $$z_2 = z_{1+1} = z_1 + (w_1+_1)2^1 = (1 + ((1+(1)4)2^0) + (1+(2)4) 2^1 = 24$$ $$z_3 = z_{2+1} = z_2 + (w_2+_1)2^2 = ((1 + ((1+(1)4)2^0) + (1+(2)4) 2^1) + (1+(3)4) 2^2 = 76 $$ I tried this but it does not seem to match my values.

$$1 + ((1+(1)4)2^0 + (1+(2)4) 2^1..... $$ $$z_n = 1 + ((1+(n-1)4)2^{n-2}) + (1+(n)4) 2^{n-1} $$

Thanks

Answer 1

Quite clearly $w_n=1+4n$. Then $$\begin{align} z_n&=z_0+\sum_{k=1}^n 2^{k-1}w_{k}\\ &=1+\sum_{k=1}^n 2^{k-1}+4\sum_{k=1}^n 2^{k-1}k\\ &=2^n\hphantom{+\sum_{k=1}^n 2^{k-1}}+4\cdot((n-1)\cdot2^n+1)\\ &=(4n-3)\cdot 2^{n}+4\end{align}$$

Indeed, this matches the recursion $$ z_0=(4\cdot 0-3)\cdot 2^0+4=1$$ and $$ z_{n-1}-z_n=(4(n+1)-3)2^{n+1}-(4n-3)2^n=(4n+5)2^n=w_{n+1}2^n$$

Answer 2

I don't know your method. if you suspect a degree two recurrence with an extra constant term, try $$ x_{n+2} = A x_{n+1} + B x_n + C $$ giving $$ \left( \begin{array}{ccc} 6 & 1 & 1 \\ 24 & 6 & 1 \\ 76 & 24 & 1 \end{array} \right) \left( \begin{array}{c} A \\ B \\ C \end{array} \right) = \left( \begin{array}{c} 24 \\ 76 \\ 212 \end{array} \right) $$ which gives $$ A = 4, B = -4, C = 4. $$ This gives Ross Millikan's sequence.

If the guess about type and degree of recurrence is correct, $$ x_{n+2} = 4 x_{n+1} -4 x_n + 4. $$ Characteristic $$ \lambda^2 - 4 \lambda + 4 = (\lambda - 2)^2 $$ is promising, owing to the repeat value, which tells us to expect $n 2^n$ as part of this. It is not difficult to finish this, see if it is realistic (it is). It gives, with $n \geq 1,$ $$ x_n = (4n-7) 2^{n-1} + 4. $$ I may have been looking at the wrong spot in Hagen's answer, since my $$ x_{n+1} = (4n-3) 2^n + 4 $$ which Hagen has in the middle somewhere.

There is a brief description of a method for this type of problem in Conway and Guy, The Book of Numbers. I believe I copied a few pages years ago, but did not make a pdf. Found a book review: it is in Chapter 3, and called the Number Wall method. Not sure whether it applies to problems with extra constant in the recursion. With no extra constant, this method has one advantage: you do not need to guess the degree ahead of time, the method tells you.I dimly recall that they had a hybrid method that included finite differences, which would solve this problem.