can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer

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


Solutions Collecting From Web of "can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer"

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


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:


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:


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:


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
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.