0
$\begingroup$

I have been given the following sequence, and told to work out the formula: $$3,15,63,255,1023,\dots$$ I noticed that each term was being multiplied by 4 and then 3 was added to get the next term. From this trend, I deduced a recursive formula of: $$T_n=4T_{n-1}+3, T_1=3$$ From common sense, I then realised that an alternative way of looking at it was that the $n$th term was equal to $4^n-1$. That is: $$T_n=4^n-1$$ My question: is there a way that I can convert the recursive sequence to the geometric sequence? My attempt is shown below:

  1. I deduced from the recursive formula that $a$ (the first term) was 3.
  2. I looked only at the section of the recursive formula that looked geometric, i.e. $4T_{n-1}$.
  3. Thus I used 4 as my common ratio $r$.
  4. I subbed these values into the geometric sequence formula $T_n=ar^{n-1}$, like so: $$T_n=3\cdot4^{n-1}$$
  5. I then added the plus 3 to this geometric sequence to get: $$T_n=3\cdot4^{n-1}+3$$

I know this is incorrect as I tested it out on the sequence and it didn't work.

$\endgroup$
0
$\begingroup$

If I have a linear recurrence $$x_n=ax_{n-1}+b$$ with given $x_1$ I can rewrite it as $$y_n=ay_{n-1}$$ with $y_n=x_n+\frac b{a-1}$. (If $a=1$ the recurrence is an arithmetic progression and has a trivial closed form). It is easy to see that $y_n$ follows a geometric progression: $$y_n=a^{n-1}y_1=a^{n-1}\left(x_1+\frac b{a-1}\right)$$ which leads to the final solution for $x_n$ as $$a^{n-1}\left(x_1+\frac b{a-1}\right)-\frac b{a-1}$$ $$=a^{n-1}x_1 + \frac b{a-1}(a^{n-1}-1)$$ For your case, $a=4$, $b=3$ and $T_1=3$, so the formula evaluates to $$T_n=3(4^{n-1}) + \frac3{4-1}(4^{n-1}-1)$$ $$=4^n-1.$$ Any linear recurrence can be solved in a similar way; see Wikipedia for more details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.