2
$\begingroup$

derive the $n^{th}$ term for the series $0,1,3,7,15,31,63,127,255,\ldots$

observation gives, $t_{n}=2^n-1$, where $n$ is a non-negative integer

$t_{0}=0$

  • 1
    *Is there a mathematical process by which we can derive this*... See my answer.2012-08-21

4 Answers 4

6

You already have an expression for the $n^{\text{th}}$ term for the sequence:

$t_{n}=2^{n}-1\tag{1}$

So let's prove this closed form by induction. Let $P(n)$ be our proposition that $t_{n}=u_{n}$, $\forall n\in\mathbb{N}\cup\{0\}$. So let us examine our basis case: $P(0)$:

$t_{0}=2^{0}-1=1-1=0=u_{0} \implies P(0) \text{ is true}$

Let us now show that if $P(k)$ is true, it follows immediately that $P(k+1)$ must also be true:

$t_{k+1}=2^{k+1}-1=2\cdot2^{k}-1=2(2^{k}-1)+1=2u_{k}+1=u_{k+1}\implies \text{ if } P(k) \text{ is true, then } P(k+1) \text{ is true}$

Therefore, as we have shown that $P(0)$ is true, and that $P(k)\implies P(k+1)$. $P(n)$ is true, $\forall n\in\mathbb{N}\cup\{0\}$.


However, if you are interested in how to actually come up with a closed form in general, a good place to start is to look at summation factors.

We can reduce a general recurrence relationship of the form:

$a_{n}T_{n}=b_{n}T_{n-1}+c_{n} \tag{2}$

To a sum, by multiplying both sides by a summation factor, denoted as $s_{n}$, such that:

$s_{n}b_{n}=s_{n-1}a_{n-1}$

In general, we can find a suitable $s_{n}$ using any multiple of the following:

$s_{n}=\frac{a_{n-1}a_{n-2}\cdots a_{1}}{b_{n}b_{n-1}\cdots b_{2}}\tag{3}$

We then have a summation recurrence, to which the solution can be found to be:

$T_{n}=\frac{1}{s_{n}a_{n}}\left(s_{1}b_{1}T_{0}+\sum_{k=1}^{n}s_{k}c_{k}\right)\tag{4}$

In your case, we have a recurrence of the form given in $(2)$:

$a_{n}=1\qquad b_{n}=2\qquad c_{n}=1$

Therefore, using $(3)$ we have $s_{n}=\frac{1}{2^{n}}$. And we can therefore plug this into $(4)$ to give:

$T_{n}=2^{n}\left(0+\sum_{k=1}^{n}{\frac{1}{2^{k}}}\right)=2^{n}\left(1-\frac{1}{2^{n}}\right)=2^{n}-1$

Which is $(1)$, the closed form you got by observation.

If you want a more complete look at solving recurrence relationships, I'd recommend the first few chapters of Concrete Mathematics by Graham, Knuth and Patashnik.

Hope this helps!

4

If the question is how to guess the form of the solution $u_n$ for every $n\geqslant0$, as opposed to, how to check that some given formula for $u_n$ is right (which is what my first comment and the other answers given so far all focus on), here is a standard computation that may help.

Assume that $u_n=au_{n-1}+b$ for every $n\geqslant1$, for some given $a$ and $b$. Thus, $u_n=f(u_{n-1})$, where the function $f$ is defined by $f(x)=ax+b$ for every $x$.One knows that to iterate a function, in general, can rapidly lead to a complicated mess (and/or to fascinating mathematics, think about fractal geometry). Some exceptions are when $f$ is constant (then $u_n=u_1$ for every $n\geqslant1$) or when $f$ is linear, so let us first assume that $f$ is linear, that is, that $f(x)=ax$ for every $x$. Then $f^{n}(x)=a^nx$ (induction over $n\geqslant1$) hence $u_n=a^nu_0$ for every $n\geqslant0$ and we are done.

The treatment of our general case $f(x)=ax+b$ cannot be made quite as simple but nearly so! To see this, we start with a simple remark. Define $v_n=u_n+c$ for some given $c$, to be chosen later. Then, $ v_n=(au_{n-1}+b)+c=a(v_{n-1}-c)+b+c=av_{n-1}+b_c,\qquad b_c=b-c(a-1). $ Thus $v_n=f_c(v_{n-1})$, where $f_c$ is a new affine function, defined by $f_c(x)=ax+b_c$, and we are still in the case we wanted to solve at the beginning, hence it seems we have been running in circles. BUT... if by chance $f_c$ is in fact linear, we are done since we know how to solve the linear case! Perhaps we happy, after all?

Which brings us to the equation $b_c=0$, solved by $c^*=b/(a-1)$ as soon as $a\ne1$. And then, everything flows easily: $v_n=av_{n-1}$ for every $n$, hence $v_n=a^nv_0$ by the preceding analysis, that is, $u_n+c^*=a^n(u_0+c^*)$, that is, $u_n=a^n(u_0+c^*)-c^*$ and we are done.

If $a=2$, $b=1$ and $u_0=0$, then $c^*=1/(2-1)=1$ and $u_n=2^n(0+1)-1=2^n-1$, which is the specific case asked about here.

Two remarks. First, once the idea explained above is understood, one can go directly from the recursion $u_n=au_{n-1}+b$ with $a\ne1$ to the solution $u_n=a^n(u_0+c^*)-c^*$ for some $c^*$ to be determined (for example, $u_1=a(u_0+c^*)-c^*$ hence $c^*=(u_1-au_0)/(a-1)$, but, to remember this exact formula is not necessary). Second, the case $a=1$ is solved by a specific (simple) analysis I will let you discover.

1

Consider the series, $0, 1, 3, 7, 15, 31, 63,\ldots$

On taking the difference between the terms one can see that the difference ceases to vanish and the difference becomes $1,2,4,8,16,32,\ldots,2^{n}$ just after the first stage. Here $n$ is a non-negative integer.

i.e. the general term of the expression is of the form $2^{(x-1)}+ax+b$

when, $x=1$, $2^{(1-1)}+a+b=0$

i.e., $a+b=-1$

when, $x=2$, $2^{(2-1)}+2a+b=1$

i.e., $2a+b=-1$

we have, $a =0$, $b=-1$

we can now conclude that the $n_{th}$ term of the series is $2^{n-1}-1$, where $n$ is a positive integer.

1

The following is a semi-formal variant of induction that is particularly useful for recurrences.

Let $x_n=2^n-1$. It is easy to verify that $x_0=0$. It is also easy to verify that $x_{n+1}=2x_n+1,$ since $2^{n+1}-1=2(2^n-1)+1$.

So the sequence $(x_n)$ starts in the same way as your sequence and obeys the same recurrence as your sequence. Thus the two sequences must be the same.