Sí, hay muchas formas de resolver esta recurrencia. El método que encontró utiliza funciones de generación y es hacia el sofisticado final. Aquí hay otros tres.
(1) averiguar y probar. Calcular los primeros términos de la secuencia:
$$\begin{array}{r|rr}n&1&2&3&4&5&6\\
T(n)&1&3&7&15&31&63
\end{array}$$
Los números en la fila inferior debe parecer familiar: son uno menos que el consecutivo de los poderes de $2$. Por lo tanto, usted podría en este punto supongo que, en general,$T(n)=2^n-1$. Por supuesto, ahora usted tiene que probar su conjetura. Normalmente, esto requiere una prueba por inducción. Conseguir la inducción de la tierra (es decir, la comprobación de la base de casos) es fácil: $T(1)=1=2^1-1$. Ahora lo que necesita para demostrar que si $T(n)=2^n-1$ es cierto cuando se $n=k$, también es cierto cuando se $n=k+1$.
Asumir como su inducción de la hipótesis de que la $T(k)=2^k-1$ algunos $k\ge 1$. Por la definición de $T$ usted saber que $T(k+1)=2T(k)+1$. Su hipótesis de inducción nos dice que $T(k)=2^k-1$, lo $T(k+1)=2(2^k-1)-1=2\cdot2^k-2+1=2^{k+1}-1$, que es exactamente lo que queríamos. Se sigue por la inducción que $T(n)=2^n-1$ todos los $n\ge 1$.
Añadido: no siempre Es tan fácil adivinar la fórmula correcta. Como Gadi Un me recuerda, hay una maravillosa herramienta disponible para ayudar con esto, el On-Line de la Enciclopedia de Secuencias de Enteros, conocido como OEIS. Si usted busca para una secuencia que contenga $\langle 1,3,7,15,31,63\rangle$, obtendrá 29 partidos, de los cuales el primero, A000225, resulta ser el más adecuado para este problema. Desde la sección de COMENTARIOS de la entrada:
También soluciones (con el mínimo número de movimientos) para el problema de Templo de Benarés, es decir, tres agujas de diamante con n discos ordenados por la disminución de tamaño en la primera aguja para colocar en el mismo orden en el tercero, sin mover más de un disco a la vez y sin colocar un disco en la parte superior de uno más pequeño.
(2) Descansar la recurrencia. Imagina que $n$ es un número bastante grande, y comenzar el cálculo de $T(n)$ en términos de los primeros términos de la secuencia hasta que punto un patrón:
$$\begin{align*}
T(n)&=2T(n-1)+1\\
&=2\big(2T(n-2)+1\big)+1\\
&=2^2T(n-2)+2+1\\
&=2^2\big(2T(n-3)+1\big)+2+1\\
&=2^3T(n-3)+2^2+2+1\\
&\qquad\qquad\qquad\vdots\\
&=2^kT(n-k)+2^{k-1}+2^{k-2}+\dots+2+1\tag{1}\\
&=2^kT(n-k)+\sum_{i=0}^{k-1}2^k\;.\tag{2}
\end{align*}$$
Ahora plug $k=n-1$ a $(2)$ para obtener $$\begin{align*}T(n)&=2^{n-1}T(1)+\sum_{i=0}^{n-2}2^i\\
&=2^{n-1}+\big(2^{n-1}-1\big)\\
&=2^n-1\;,
\end{align*}$$
donde he utilizado la fórmula para la suma de una serie geométrica para evaluar la suma.
Si se utiliza este enfoque, a continuación, usted debe ir a probar la fórmula por medio de la inducción, al igual que en el método anterior, ya que la fórmula en $(1)$ fue una conjetura $-$ muy sólido, supongo, pero todavía una conjetura necesidad de prueba.
Otro punto a notar aquí es que el último paso ha sido un poco más fácil si hubiéramos retrocedido la secuencia mediante el cálculo de $T(0)$ a partir de $T(1)$: $T(0)=\frac12\big(T(1)-1\big)=0$. Entonces podríamos haber sustituido $k=n$ a $(2)$ para obtener el resultado deseado directamente.
(3) en cuanto a la no-homogénea de recurrencia en un homogéneo por un cambio de variable. Deje $S(n)=T(n)+d$ para algunos aún desconocidos $d$. A continuación,$T(n)=S(n)-d$, y la recurrencia puede escribirse como
$$\begin{align*}
S(n)-d&=\begin{cases}2\big(S(n-1)-d\big)+1,&\text{if }n>1\\
1-d,&\text{if }n=1
\end{casos}\\\\
y=\begin{cases}
2S(n-1)-2d+1,&\text{if }n>1\\
1-d,&\text{if }n=1\;.
\end{casos}
\end{align*}$$
Mover las constantes a la derecha en la recurrencia: $$S(n)=2S(n-1)-d+1\;.$$ Thus, if we set $d=1$, we get rid of the constant term: $$S(n)=2S(n-1)\;.$$ This is just exponential growth: $S(n)$ doubles with each increase of $1$ in $n$. And $$S(1)=T(1)+d=1+1=2=2^1\;,$$ so it's very easy to see that $S(n)=2^n$ for every $n\ge 1$. Finally, $T(n)=S(n)-d=2^n-1$.
Para tu segunda pregunta, yo podría cocinar otros ejemplos, pero la Torre de Hanoi problema es por lejos el mejor conocido, para satisfacer esta recurrencia.
