Intereting Posts

Bijection between power sets of sets implies bijection between sets?
Alternating sum of binomial coefficients
Floor and Ceiling function
How to show that $\frac{1}{\tan(x/2)}=2 \sum_{j=1}^{\infty}\sin(jx)$ in Cesàro way/sense?
How to prove that exists distinct $x_1,x_2 \in(a,b)$ such that $f '(x_1)f '(x_2)=1$?
If p is an odd prime, prove that $1^2 \times 3^2 \times 5^2 \cdots \times (p-2)^2 \equiv (-1)^{(p+1)/2}\pmod{p}$
Is there much of difference between set models and class models?
Finding the antiderivative of the product of two functions given only their derivative properties
Reverse Markov Inequality for non-negative unbounded random variables
Product of two probability kernel is a probability kernel?
Find formula for number of dominated vectors in partial order
What are the odd of a single coin toss after many consecutive ones?
Prove that $x^2<\sin x \tan x$ as $x \to 0$
Continuity of analytic function implies convergence of power series?
The last 2 digits of $7^{7^{7^7}}$

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$

- Is $\Delta_0=\Delta_1$ in arithmetical hierarchy?
- How to convert a hexadecimal number to an octal number?
- Formal proof for $(-1) \times (-1) = 1$
- Is there any simple method to calculate $\sqrt x$ without using logarithm
- How to get the aspect ratio of an image?
- nth roots of negative numbers

- How to find the limit of the sequence $x_n =\frac{1}{2}$, if $x_0=0$ and $x_1=1$?
- I have simple multiplication confusion, any help would be great
- $T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer
- Prove that $\sqrt{7}^{\sqrt{8}}>\sqrt{8}^{\sqrt{7}}$
- Is $2^k = 2013…$ for some $k$?
- Solving a recurrence relation with the characteristic equation
- Recursive square root problem
- Prove $\frac{1}{a^3+b^3+abc}+\frac{1}{a^3+c^3+abc}+\frac{1}{b^3+c^3+abc} \leq \frac{1}{abc}$
- How to get the characteristic equation from a recurrence relation of this form?
- What is zero times infinity?

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!

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.

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.

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.

- How many possibilities to arrange a rope of length $N$ between two points
- At most one subgroup of every order dividing $\lvert G\rvert$ implies $G$ cyclic
- Prove $ \sum \frac{\cos n} { \sqrt n}$ converges
- Is this space complete?
- How do I prove that 15462227 and 15462229 relatively prime?
- normal bundle of level set
- Parametric curve on cylinder surface
- Determining whether there are solutions to the cubic polynomial equation $x^3 – x = k – k^3$ other than $x = -k$ for a given parameter $k$
- Brownian Motion Conditional Expectation Question
- Colliding Bullets
- Number of singular $2\times2$ matrices with distinct integer entries
- Need the norm of positive number be positive?
- Expectation of pairwise differences between uniform random points in hypercube
- What is the best way to show that the exponential sequence doesn't uniformally converge on an unbounded interval
- $f(g(x))=g(f(x))$ implies $f(c)=g(c)$ for some $c$