2

I am given the following recurrence relation: $a_{n+1} = 3a_n+1$ where $a_0 = 1$ which gives these values for the first 5 numbers: $1, 4, 13, 40, 121$, where I must find a specific formula $a_n$ how would I go about calculating the conjecture for this?

It's clear to me it follows the standard of an arithmetic series, though what are the steps to figuring it out?

Here is my rational so far (after some digging):

$a_1 = 1$ $a_2 = 3a_1+1 = 4$ $a_3 = 3a_2+1 = 13$ $a_4 = 3a_3+1 = 40$ $a_5 = 3a_4+1 = 121$

Then taking the differences of the result:

difference between $1 \& 4 = 3; 4\&13 = 9; 13\&40 = 27; 40\&121 = 81$

Then taking the differences of the differences:

difference between $3\&9 = 6; 9\&27 = 18; 27\&81 = 54$

again ...

$6\&18 = 12; 18\&54 = 36$

$12\&36 = 24$

Get the last number in its lowest term which is $24/12 = 2$

Hence the series must be divisible by 2.

Given that each difference is $3^n$

We then get: $\frac{3^na_n-1}{2}$ because of $a_0 = 1$ we must minus by 1 to get the term $a_0=1$

Stackcans
  • 361
  • 2
    Sorry if this is a silly question, but what do you mean by "the conjecture" in this case? Are you looking for the general expression for $a_n$ ? – Matti P. Aug 06 '21 at 07:47
  • 2
    You cannot calculate a conjecture. You can formulate it. – Gary Aug 06 '21 at 07:48
  • @MattiP I was imitating the language from a book I was reading that mentioned 'we can easily conjecture that $a_m$ = ...' for a similar series like-so. – Stackcans Aug 06 '21 at 07:51
  • Probably this way of writing helps: $a_0 = 1, a_1 = 3 + 1, a_2= 9 + 3 + 1,a_3 = 27+9+3+1,...$ – Lukas Betz Aug 06 '21 at 08:19
  • After doing some digging on Stack mathematics I found this link here: conjecture - The second answer led me to the method of differences and recursion that has been very helpful in interpreting series like this. – Stackcans Aug 06 '21 at 08:20
  • @LukasBetz That helps tremendously! Although there must be some techniques for computing a formula from this. I found that a polynomial was one way though I cannot seem to understand how it is done – Stackcans Aug 06 '21 at 08:23
  • 1
    Note that the concept you are talking about here is a sequence not a series. – Gary Aug 06 '21 at 09:14
  • Welcome to Mathematics Stack Exchange. At one point you said $a_0=1$, and at another you said $a_1=1$!? – J. W. Tanner Aug 06 '21 at 14:52
  • @Stackcans Alt. hint: $,a_{n+1} = 3a_n+1 \iff a_{n+1} + \frac{1}{2}=3\left(a_n+\frac{1}{2}\right),$, so $,a_n+\frac{1}{2},$ must be a geometric progression. – dxiv Aug 07 '21 at 01:49

1 Answers1

2

We are given the recurrence system $$a_{n+1}=3a_n+1,\\a_0=1.$$ Preliminary observations: Its difference equation is a first-order linear recurrence relation, which generates a sequence in which the consecutive differences between consecutive terms have a common ratio, i.e., the difference between consecutive terms is successively multiplied by a common ratio. (In our example the common ratio is $3$.) Arithmetic and geometric sequences are actually special cases of such a sequence.

We can derive its closed form (general term) using the formula for geometric series:

$$a_0=1\\ a_1=3+1\\ a_2=3^2+3+1\\ a_3=3^3+3^2+3+1\\ a_4=3^4+3^3+3^2+3+1\\ \cdots\\ a_n=3^n+\frac{1(3^n-1)}{3-1}\\ =\frac123^{n+1}-\frac12\quad(n\geq0).$$

In general, when $r\neq1,$ the recurrence relation $a_{n+1}=ra_n+d$ has closed form $$a_n=a_0r^n+\frac{d(r^n-1)}{r-1}\quad(n\geq0).$$ Since this is of the form $$a_n=\alpha r^n+\beta,\tag{*}$$ once a sequence has been identified as such, we can simply plug $n=0,1$ into $(\text*)$ to form a pair of simultaneous linear equations then solve for $\alpha$ and $\beta.$

ryang
  • 38,879
  • 14
  • 81
  • 179