Résolution des récidives par induction

Question

Problème: $T(0)=0, T(1)=1$ et $T(n)=T(n-1)+T(n-2)$ $\forall n\geq 2$

Donné $T(2n)=T(n-1)T(n)+T(n)T(n+1)$ $\forall n\geq 1$, prouvez par récurrence que $T(2n)=T(n+1)^2 -T(n-1)^2$ $\forall n \geq 1$

Ma tentative :

Cas de base :$T(0)=0$, $T(1)=1$

Hypothèse inductive : supposer$T(2n)=T(n+1)^2-T(n-1)^2$ pour $n=k$ $\forall n \geq 1$

Étape inductive : montrer que l'hypothèse inductive fonctionne pour$n=k+1$

\begin{align} T(2(n+1)) &= T(2n+2)\\ &= T((2n+1)-1) + T((2n+1)-2)&&\text{By definition}\\ &= T(2n+1) + T(2n)&&\text{Simplify}\\ &= T(2n+1) + T(n+1)^2 - T(n-1)^2&&\text{Apply hypothesis} \end{align}

Mais après cela, je suis perplexe. Je ne sais pas comment continuer cette preuve, ou si c'est une impasse. Toute aide serait grandement appréciée!

Answer 1

Pour le cas de base, c'est-à-dire pour $n = 1$, tu as $T(2) = T(1) + T(0) = 1$, donc

$$T(2) = 1 = 1^2 - 0^2 = T(2)^2 - T(0)^2 \tag{1}\label{eq1A}$$

Pour l'étape inductive, c'est-à-dire, $n = k + 1$, en utilisant le premier donné $T(2n)$ formule, plus de l'énoncé du problème que $T(k+2) = T(k+1) + T(k) \implies T(k+1) = T(k+2) - T(k)$, donne

$$\begin{equation}\begin{aligned} T(2(k+1)) & = T((k+1)-1)T(k+1) + T(k+1)T((k+1)+1) \\ & = T(k)T(k+1) + T(k+1)T(k+2) \\ & = T(k)(T(k+2) - T(k)) + (T(k+2) - T(k))T(k+2) \\ & = T(k)T(k+2) - T(k)^2 + T(k+2)^2 - T(k)T(k+2) \\ & = T(k+2)^2 - T(k)^2 \\ & = T((k+1)+1)^2 - T((k+1)-1)^2 \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Ceci termine l'étape inductive, c'est-à-dire que la formule fonctionne pour $n = k + 1$, donc par récurrence la deuxième formule pour $T(2n)$ fonctionne pour tous $n \ge 1$. Cependant, notez que cela n'utilise pas réellement, ni n'a besoin de, l'étape d'hypothèse inductive, donc cela aurait pu être prouvé directement à la place du$T(2n)$ expression.

Une autre chose à noter est la récurrence $T(n)$ est en fait $F_n$, c'est-à-dire la séquence de Fibonacci .