Recurrence problem T(n) = 2T(n − 1) + 1
Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$.

Method 1: Guessing

Here are some values of $T(n)$:
$$
\begin{array}{c|cccccc}
n &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\\hline
T(n) &amp; 0 &amp; 1 &amp; 3 &amp; 7 &amp; 15 &amp; 31
\end{array}
$$
If you're familiar with powers of 2, you will recognize that $T(n) = 2^n-1$. If not, you can look it up on the Online Encyclopedia of Integer Sequences, where you will find it as A000225, under the name Mersenne numbers.

Method 2: Homogenization

We look for a related recurrence without the "$+1$". The first think one could try is replacing $T(n)$ with $S(n) = T(n) + C$, which satisfies the recurrence
$$ S(n) = T(n) + C = 2T(n-1) + C + 1 = 2S(n-1) - C + 1. $$
We see that if $C = 1$ then $S(n) = 2S(n-1)$, and so $S(n) = 2^n S(0) = 2^n$. We conclude that $T(n) = 2^n - 1$.

Method 3: Reduction

The recurrence makes it clear that the first order asymptotics of $T(n)$ should be related to $2^n$, and so suggests considering $R(n) = T(n)/2^n$, which satisfies the recurrence
$$ R(n) = \frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + \frac{1}{2^n} = R(n-1) + \frac{1}{2^n}. $$
This shows that
$$
R(n) = R(0) + \sum_{m=1}^n \frac{1}{2^m} = 1 - \frac{1}{2^n},
$$
and so $T(n) = 2^n - 1$.

If we are only interested in the asymptotics, we could notice that since the series $\sum_{n=1}^\infty \frac{1}{2^n}$ converges, we clearly have $R(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.

Method 4: Generating series

We could also solve the recurrence automatically using generating series. Let
$$ P(x) = \sum_{n=0}^\infty T(n) x^n. $$
Then
$$ P(x) = T(0) + \sum_{n=1}^\infty T(n) x^n = 2\sum_{n=1}^\infty T(n-1) x^n + \sum_{n=1}^\infty x^n = 2xP(x) + \frac{x}{1-x}. $$
We conclude that
$$ P(x) = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x} = \sum_{n=0}^\infty (2^n - 1) x^n. $$
Therefore $T(n) = 2^n - 1$.

Method 5: Combinatorial interpretation

This method is more creative. We find some combinatorial object which we already know how to count, and we show that it satisfies the same recurrence. In this case, we could choose all non-empty subsets of $\{1,\ldots,n\}$. Each such subset is either obtained from a non-empty subset of $\{1,\ldots,n-1\}$ by either adding or not adding $n$, and additionally the subset $\{n\}$, which does not arise in this way. The base cases also match, and so $T(n) = 2^n - 1$.