The sequence $<a_n>$ is defined as follows, $a_1=a_2=1$, $a_3=2$,
$$a_{n+3}=\frac{a_{n+2}a_{n+1}+n!}{a_n},$$$n \ge 1$.
Prove that all the terms in the sequence are integers.
We will prove that $a_n=(n-1)\cdot a_{n-2}$, whence the conclusion follows.
Indeed, the base case holds, as $a_3=2\cdot 1=2$. Now, assume the hypothesis holds for all $k<n+2$. Then $$a_{n+3}=\frac{(n+1)a_n\cdot a_{n+1}+n!}{a_n}=(n+1)a_{n+1}+\frac{n!}{a_n}$$
But by the inductive hypothesis, $$a_{n+1}a_n=na_{n-1}\cdot (n-1)a_{n-2}=n(n-1)(n-2) a_{n-3} (n-3) a_{n-4}=\dots=n!$$so that $$a_{n+3}=(n+1)a_{n+1}+\frac{n!}{a_n}=(n+1)a_{n+1}+a_{n+1}=(n+2)a_{n+1}$$completing the induction$.\:\blacksquare\:$
Not really. If you start with a recursive definition, induction is the tool to prove anything. Whatever you use to find a pattern, you're going to prove it works using the recursion and previous instances of the pattern - which is recursion.
Incidentally, $a_{n+3}=\frac{a_{n+2}a_{n+1}+1}{a_n}$ with the same initial conditions also leads to an all-integer sequence.
jmerry wrote:
Not really. If you start with a recursive definition, induction is the tool to prove anything. Whatever you use to find a pattern, you're going to prove it works using the recursion and previous instances of the pattern - which is recursion.
Incidentally, $a_{n+3}=\frac{a_{n+2}a_{n+1}+1}{a_n}$ with the same initial conditions also leads to an all-integer sequence.
Can you show the proof of $a_{n+3}=\frac{a_{n+2}a_{n+1}+1}{a_n}$ plz...
Reconstructing some stuff I worked up in 1998 or 1999:
Consider a doubly infinite sequence of real numbers $a_n$, satisfying $a_n a_{n+3}=a_{n+1} a_{n+2}+1$ for all $n\in\mathbb{Z}$. The recurrence can be solved either for $a_n$ or $a_{n+3}$ in terms of the other three, allowing us to continue the sequence both forward and backwards uniquely - except when we hit a zero, in which case there are many possibilities for the terms three steps away.
Lemma: If three consecutive members of the sequence are all positive, $a_n$ is positive for all $n$.
Proof: Induction, of course. If $a_n,a_{n+1},a_{n+2}$ are all positive, $a_{n+3}=\frac{a_{n+1}a_{n+2}+1}{a_n}>0$ and $a_{n-1}=\frac{a_{n}a_{n+1}+1}{a_{n+2}}>0$.
Lemma: If six consecutive terms of the sequence are integers and $a_n$ is never zero, then all terms of the sequence are integers.
Proof: We derive a different recurrence for the sequence. Summing two cases of the original recurrence:
\begin{align*}a_n a_{n+3} &= a_{n+1}a_{n+2}+1\\
a_{n+3}a_{n+4}+1 &= a_{n+2}a_{n+5}\\
a_{n+3}(a_n+a_{n+4}) &= a_{n+2}(a_{n+1}+a_{n+5})\\
\frac{a_n+a_{n+4}}{a_{n+2}} &= \frac{a_{n+1}+a_{n+5}}{a_{n+3}} =k\end{align*}By induction, and the assumed act that the denominators are never zero, this $k$ is independent of $n$. Consider the case in which $a_n$ through $a_{n+5}$ are the six known integer members of the sequence. Then $k$ is rational, and its denominator in lowest terms divides both $a_{n+2}$ and $a_{n+3}$. But, since $a_n a_{n+3}=a_{n+1} a_{n+2}+1$, $a_{n+2}$ and $a_{n+3}$ must be relatively prime. That makes $k$ an integer, and we have $a_{n+4}=ka_{n+2}-a_n$ for all $n$. That's linear with constant coefficients; if we start with four consecutive integer values and move forward, we get nothing but integers as $n$ increases to $\infty$. Similarly, $a_{n-4}=ka_{n-2}-a_n$ and we get nothing but integers as $n$ decreases to $-\infty$.
If we start with initial conditions $a_0=1,a_1=1,a_2=2$, we get $a_{-1}=1$, $a_{-2}=2$, and $a_3=3$ by routine calculation. That's enough to apply the lemma, with $k$ for this sequence being $4$.
But of course, I didn't stop there. No, I was interested in more than just those initial conditions. What other all-integer sequences are possible with this recursion?
First, the all-positive case:
Consider the products $c_n=a_n a_{n+1}$. Since they're all positive integers, they have a minimum. WLOG, let $c_0$ be that minimum. Then, since $a_0 a_1 \le a_1 a_2$, $a_0\le a_2$. Similarly, form $a_0 a_1\le a_{-1} a_0$, $a_1\le a_{-1}$. But we also have $a_{-1} a_2 = a_0 a_1 +1$; if both $a_1<a_{-1}$ and $a_0<a_2$, the products $a_0 a_1$ and $a_{-1}a_{-2}$ would differ by more than $1$. That means that one of those pairs is equal; WLOG, $a_1=a_{-1}$. Then $a_{-1}a_2=a_1 a_2=a_0 a_1+1$ implies $a_1=1$ and $a_2=a_0+1$.
So, this case reduces to considering a single family of initial conditions $a_1=a_{-1}=1$ and $a_0$ variable. Choosing $a_0$ a positive integer gets us $a_2$ and $a_{-2}$ positive integers for free. Then $a_3=\frac{a_1 a_2+1}{a_0}=\frac{a_2+1}{a_0}=\frac{a_0+2}{a_0}$ is an integer if and only if $a_0=1$ or $a_0=2$.
The sequences of positive integers satisfying this recursion are $1,1,1,2,3,7,11,26,41,97,\cdots$, $1,2,1,3,2,7,5,18,13,47,\cdots$, and index shifts thereof. The $k$-values for these sequences are $4$ and $3$ respectively.
The all-negative case is exactly like the all-positive case by symmetry of the defining recursion. Nothing new, so move on.
Allowing mixed signs but still no zeros, we seek to minimize $|a_n a_{n+1}|$. Again WLOG, this occurs at $n=0$, giving $|a_1|\le |a_{-1}|$ and $|a_0|\le |a_2|$. Again, strict inequality in both cases would have $|a_{-1} a_2 - a_0 a_1| >1$, so WLOG $|a_{-1}|=|a_1|$. From $a_{-1}a_2-a_1 a_0=1$, $a_{-1}$ and $a_1$ are relatively prime, and both are $\pm 1$.
Case 1: $a_1=a_{-1}=1$. A positive $a_0$ would put us in the all-positive case, so we may take $a_0$ negative. Then $a_2=a_0+1$ and $|a_2|<|a_0|$, contradicting the assumption of minimality.
Case 2: $a_1=1$, $a_{-1}=-1$. Then $a_2=\frac{a_0 a_1+1}{a_{-1}}=-a_0-1$ and $a_{-2}=\frac{a_0 a_{-1}+1}{a_{1}} = -a_0+1$. One of these is closer to zero than $a_0$, again contradicting mimimality.
The other sign possibilities can be obtained from the above by flipping the sign of the sequence. We have shown that there are no all-integer sequences with mixed signs and no zeros.
Finally, we consider allowing zeros. Suppose $a_0=0$. Then, since $a_1 a_2=a_0 a_3-1=-1$, $a_1$ and $a_2$ are $1$ and $-1$ in some order. WLOG, make that $a_1=1$ and $a_2=-1$. What is $a_3$? Solving the equation gives $\frac{0}{0}$, and $a_3$ can be anything at all.
As it turns out, all integer choices for $a_3$ give integer sequences, at least on that side. For $a_2\in \{0,1,2\}$, these sequences come back around to zero in various finite lengths of time, allowing us to choose again (and possibly introduce non-integer values). For other values, the sequence never returns to zero and is deterministic on that side. The $k$-value for such a sequence is $a_3-1$.
That's everything, or at least as close as we can get given the complexity of the cases with zeros.
Far more than you asked for, but I came up with this stuff a long time ago and felt like bringing it out again.