A prueba por la inducción fuerte que $a_n\le3^n$ donde $a_n=a_{n-1}+a_{n-2}+a_{n-3}$

Question

No estoy seguro de si esto es correcto. Cualquiera puede verificar, si esta prueba es válida? Gracias!

Definir una secuencia $\{a_n\}_{n\ge0}$ como sigue: $$a_0=1,\qquad,a_1=3,\qquad,a_2=9,\qquad,a_n=a_{n-1}+a_{n-2}+a_{n-3}\text{ for }n\ge3.$$ Demostrar que para cualquier entero positivo $n$, $a_n\le3^n$.

---

Prueba. Vamos $P(n)$: $a_n\le 3^n$, $n$ es un entero no negativo.

(i) caso Base:

• Considerar al $n=0$. LHS$=a_0=1$, RHS=$3^0=1$ $\therefore$ LHS$\le$HR, a continuación, $P(0)$ mantiene.
• Considerar al $n=1$. LHS$=a_1=3$, RHS=$3^1=3$ $\therefore$ LHS$\le$HR, a continuación, $P(1)$ mantiene.
• Considerar al $n=1$. LHS$=a_2=9$, RHS=$3^2=9$ $\therefore$ LHS$\le$HR, a continuación, $P(2)$ mantiene.

(ii) Inductivo caso:
Suponga $P(i)$ es cierto para $0 \le i \le k$, $k\ge2$.

(iii) Inductivo conclusión: Considerar $n=k+1$. $$ \begin{align*} \mathrm{LHS}=a_{k+1}&=a_k+a_{k-1}+a_{k-2} \qquad\text{(by definition, since %#%#%)}\\ &\le 3^k+3^{k-1}+3^{k-2} \qquad\text{(by Induction Hypothesis)}\\ &=3^k(3^{-1}+3^{-2}+3^{-3})\\ &=3^k\left(\frac13+\frac19+\frac1{27}\right)\\ &=\frac{13}{27} 3^k\\ &\le 3^{k+1} = \mathrm{RHS} \end{align*} $$ Por lo tanto, por el Principio de la Fuerte Inducción, $k\ge 2$ es cierto para todos no negativos enteros positivos $P(n)$.

Answer 1

Buena reseña; ¡se ve muy bien! Tal vez una manera un poco resbaladizo de hacer el paso de la inducción (y probablemente lo que pretendía hacer el problema) es observar que:\begin{align*} 3^k + 3^{k-1} + 3^{k-2} &< 3^k + (3)3^{k-1} + (3^2)3^{k-2} \\ &= 3^k + 3^k + 3^k \\ &= 3(3^k) \\ &= 3^{k+1} \end{align*}