Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
9  
Let $s_n=t_n+1$, then $s_{n+1}=2s_n$ and $s_0=1$, end of story. –  Did Aug 17 '12 at 12:14
    
NOTE: We get $t_{n}=2^n-1$ by observation. Is there a mathematical process by which we can derive this. –  Rajesh K Singh Aug 17 '12 at 12:28
    
There is a long discussion at en.wikipedia.org/wiki/Recurrence_relation which shows some techniques to find these solutions. Without the constant (1) and the initial condition, the solution is a2^n. did's shift gets rid of the constant. –  Ross Millikan Aug 17 '12 at 12:54
1  
Is there a mathematical process by which we can derive this... See my answer. –  Did Aug 21 '12 at 9:34
add comment

4 Answers

up vote 6 down vote accepted

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!

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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