\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#2: Solutions
\end{center}
\medskip
\begin{enumerate}
\item {\it Find necessary and sufficient conditions
for the infinite product $f_1 f_2 f_3 \cdots$ to converge
in the ring of formal power series.
Be sure to take proper care of degenerate cases,
e.g., where one of the $f_n$'s actually is 0.
A detailed proof is not required.}
There are three ways for such a product to converge.
First, one of the $f_n$'s could be 0,
in which case the product is 0.
Second, infinitely many of the $f_n$'s could be of positive order
(i.e., could have constant term 0),
in which case the product is again 0.
Third, it could be the case that $f_n \rightarrow 1$,
i.e., that $\mbox{ord}(f_n-1) \rightarrow \infty$,
in which case the infinite product still converges
(to something non-zero, unless one of the factors is zero
as in the first case).
Here is a more rigorous analysis.
If $f_n$ is 0 for some $n$,
the infinite product converges to 0.
Now suppose none of the $f_n$'s is 0;
then each factor in the infinite product has finite order.
Suppose that infinitely many of the factors have positive order
(i.e., are divisible by $x$).
Then the infinite product again converges to 0.
On the other hand, suppose
(still assuming that all of the $f_n$'s are non-zero)
that only finitely many of the factors have positive order;
that is, suppose that all but finitely many have order 0.
If we let $N$ denote the sum of the orders of those factors,
then we find that $f_1 f_2 \cdots f_n$ is never divisible by $x^{N+1}$,
no matter how big $n$ is, which means that the infinite product
cannot converge to 0.
Now, suppose $f_1 f_2 \cdots f_n \rightarrow g$
for some non-zero formal power series $g$.
For convenience, we will write the partial product
$f_1 \cdots f_n$ as $F_n$.
Since $F_{n-1} \rightarrow g$,
we may appeal to the continuity of division
to infer that $f_n = F_{n}/F_{n-1} \rightarrow 1$.
Conversely, suppose $f_n \rightarrow 1$,
so that $\mbox{ord}(f_n-1) \rightarrow \infty$.
The relation $F_{n} - F_{n-1} = F_{n-1} (f_n-1)$
gives $\mbox{ord}(F_n-F_{n-1}) \geq \mbox{ord}(f_n-1)$,
and since $\mbox{ord}(f_n-1) \rightarrow \infty$,
we have $\mbox{ord}(F_n-F_{n-1}) \rightarrow \infty$ as well
(or equivalently $F_n - F_{n-1} \rightarrow 0$).
But this implies that the infinite series
$F_1 + (F_2-F_1) + (F_3-F_2) + \cdots$ is convergent,
which (by telescoping) is tantamount to
the assertion that the sequence $F_1,F_2,F_3,\dots$ converges,
which means that the infinite product $f_1 f_2 f_3 \cdots$ converges.
\item {\it By comparing the expansions of
$1/(1-x-x^2)$ and $1/(1-x-y)$,
derive a formula for the Fibonacci numbers
as sums of binomial coefficients.}
Specializing
$1/(1-x-y) = \sum_{n=0}^\infty \sum_{k=0}^n {n \choose k} x^k y^{n-k}$
to $y=x^2$,
we get
$1/(1-x-x^2) = \sum_{n=0}^\infty \sum_{k=0}^n {n \choose k} x^{2n-k}$.
So the Fibonacci number $F_m$, being equal to
the coefficient of $x^m$ in the formal power series expansion of $1/(1-x-x^2)$,
must also be equal to $\sum {n \choose k}$, where the sum is taken
over all $n,k$ with $0 \leq k \leq n$ and $2n-k=m$.
These pairs are $(n,k) = (m,m),(m-1,m-2),(m-2,m-4),\dots$,
so $F_m = {m \choose m} + {m-1 \choose m-2} + {m-2 \choose m-4} + \dots$,
where the sum stops whenever the lower index is 0 (for $m$ even)
or 1 (for $m$ odd).
Example: $F_4 = {4 \choose 4} + {3 \choose 2} + {2 \choose 0}
= 1 + 3 + 1 = 5$
and $F_5 = {5 \choose 5} + {4 \choose 3} + {3 \choose 1}
= 1 + 4 + 3 = 8$.
\end{enumerate}
\end{document}