ISL 83

[ma_go]

sia $ F_n $ la successione dei numeri di Fibonacci, e sia $ P(x) $ un polinomio di grado $ 990 $ tale che $ P(k) = F_k $ $ \forall k \in \{992, ..., 1982\} $.
dimostrare che $ P(1983) = F_{1983} - 1 $

[dario2994]

Continuo le riesumazioni casuali.
Sia $I_k=\{k+2,k+3,\dots, 2k+2\}$.
Sia $A_k$ l'insieme dei polinomi $P$ di grado $k$ tali che $P(n)=F_n\ \forall\ n\in I_k$.

Dimostro per induzione su $k$ che $P(2k+3)=F_{2k+3}-1$

• P.B. $k=0$ I polinomi in $A_0$ sono costanti e sono tali che $P(2)=F_2=1$, allora $P(x)=1$ è un'identità. E allora $P(3)=1=2-1=F_{2\cdot 0+3}-1$.
• P.I. $k\to k+1$ Sia $P(x)\in A_{k+1}$. Definisco $Q(x)=P(x+2)-P(x+1)$. Banalmente $Q(x)$ ha grado $k$.
  Inoltre dato che $n\in I_k\to (n+1,n+2)\in I_{k+1}$ vale anche:
  $\forall n\in I_k: Q(n)=P(n+2)-P(n+1)=F_{n+2}-F_{n+1}=F_n$
  Ma allora $Q(x)\in A_k$ e perciò per ipotesi induttiva $Q(2k+3)=F_{2k+3}-1$. E perciò:
  $P(2(k+1)+3)=P(2(k+1)+2)+Q(2(k+1)+1)=F_{2k+4}+F_{2k+3}-1=F_{2(k+1)+3}-1$
  Che era quello che volevo dimostrare.

E la tesi del problema ne segue banalmente dato che $P\in A_{990}$ per definizione di $A_{990}$ e allora per quanto dimostrato $P(1983)=P(2\cdot 990+3)=F_{2\cdot 990+3}-1=F_{1983}-1$.