귀납법으로 재발 해결

Question

문제: $T(0)=0, T(1)=1$ 과 $T(n)=T(n-1)+T(n-2)$ $\forall n\geq 2$

주어진 $T(2n)=T(n-1)T(n)+T(n)T(n+1)$ $\forall n\geq 1$, 귀납적으로 증명 $T(2n)=T(n+1)^2 -T(n-1)^2$ $\forall n \geq 1$

내 시도 :

기본 케이스 :$T(0)=0$, $T(1)=1$

귀납적 가설 : 가정$T(2n)=T(n+1)^2-T(n-1)^2$ ...에 대한 $n=k$ $\forall n \geq 1$

귀납적 단계 : 귀납적 가설이 작동하는 것을 보여줍니다.$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}

하지만 그 후 나는 당황합니다. 이 증명을 계속하는 방법이나 이것이 막 다른 골목인지 잘 모르겠습니다. 어떤 도움이라도 대단히 감사하겠습니다!

Answer 1

기본 케이스의 경우, 즉 $n = 1$, 당신은 $T(2) = T(1) + T(0) = 1$, 그래서

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

귀납적 단계의 경우, 즉, $n = k + 1$, 주어진 첫 번째 사용 $T(2n)$ 공식, 플러스 문제 진술에서 $T(k+2) = T(k+1) + T(k) \implies T(k+1) = T(k+2) - T(k)$, 제공

$$\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}$$

이것은 유도 단계를 완료합니다. 즉, 공식이 $n = k + 1$그래서 두 번째 공식은 $T(2n)$ 모두를 위해 작동 $n \ge 1$. 그러나 이것은 귀납 가설 단계를 실제로 사용하지도 필요하지도 않습니다. 따라서 이것은 실제로 주어진$T(2n)$ 표현.

주목해야 할 다른 사항은 재발입니다. $T(n)$ 실제로 $F_n$, 즉 피보나치 수열 .