N-nacci Identities: The Final Question (Generalizing Time!)

Question

Okay so here is my personal work on the problem set. I only have question 5 remaining which involves generalization of any recursive sequence. $n$'s correspond to the $n$ in n-nacci.

I hope to write a paper in which I discuss my results and to devise a theorem describing a method which to find any ath term of a recursion sequence. (Beginning with a n-nacci sequence)

Links to previous postings: Fibonacci Numbers - Complex Analysis

Fibonacci( Binet's Formula Derivation)-Revised with work shown

Here's my attempt on the problem set on page 106 thus far: (Number 5 being the only question that I have left) http://www.math.binghamton.edu/sabalka/teaching/09Spring375/Chapter10.pdf

(2) To derive a generating function for $f_a$, note that the n-nacci series is defined by the sequence of numbers $f_a = f_{a-1}+f_{a-2}+f_{a-3} \cdots + f_{a-n}, \ldots )$.
If we break this up into $n+1$ separate generating functions and sum them to obtain the generating function $F(z)$ it will look something like:
for a $F(z) = f_0+f_1z+f_2z^2+...+f_az^a$

$$(0,1,0,0,0...) \rightarrow\,z)$$ $$+(0,f_0,f_1,f_2, \cdots )\to\,zF(z)$$ $$+ (0,0,f_0,f_1,f_2, \cdots )\to z^2F(z)$$
$$+ (0,0,0,f_0,f_1,f_2, \cdots )\to z^3F(z)$$ $ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \small \bullet $
$ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \small \bullet $
$ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \small \bullet $ $$+ (0_1,0_2,0_3, \cdots ,0_n,f_0,f_1,f_2, \cdots )\to z^nF(z)$$ This all equals $$(0,1, \cdots f_{a-1}+f_{a-2}+f_{a-3} + \cdots +f_{a-n})\to z+zF(z)+z^2F(z)+z^3F(z) + \cdots + z^nF(z)$$
Therefore $F(z)=z+zF(z)+z^2F(z)+z^3F(z) + \cdots + z^nF(z)$, solving for $F(z)$ we obtain
$$F(z) = \frac {z}{1-z-z^2-z^3- \cdots - z^n} \bullet$$
Am I on the right track?

~

I felt that it would make more sense to do (2) before (1) here's (1)
*First note that by the quadratic formula, the two roots of the denominator are $\varphi,\bar \varphi$ where $\varphi= \frac {1+\sqrt5}{2}$.
$$\lim_{n\to\infty}\left|\frac{f_{n+1}z^{n+1}}{f_nz^n}\right|=|z|\lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\varphi|z|\;,$$

so the radius of convergence is $\dfrac1\varphi=\dfrac{-1+\sqrt5}2$
Don't have any clue how to generalize this to a n-nacci sequence.

~

(3)
$Res(f,c) = \frac{1}{a-1!}\lim_{z\to c}\frac{d^a-1}{dz^a-1} ((z-c)^aF(z)$ for a pole of order $a$.

$$1=Res_{z=0}z^{-1}$$ then $z^{a+1}$ would be the extracting term:
$$f_a=Res_{z=0}\frac{1}{z^{a+1}} \sum_{n>1}{f_az^a}$$

Could I instead generalize this to?

$$\operatorname {Res}_{z=0}\left(\frac{z}{z^{a+1}(1-z-z^2-z^3- \cdots -z^n)}\right)$$
$$\begin{align*} &=\frac1{a!}\lim_{z\to 0}\frac{d^a}{dz^a}\left(z^{a+1}\frac{z}{z^{a+1}(1-z-z^2-z^3- \cdots - z^n)}\right)\\ &=\frac1{a!}\lim_{z\to 0}\frac{d^a}{dz^a}\big(F(z)\big)\\ &=\frac1{a!}\lim_{z\to 0}\frac{d^a}{dz^a}\sum_{k\ge 0}f_kz^k\\ &=\frac1{a!}\lim_{z\to 0}\sum_{k\ge 0}f_k\frac{d^a}{dz^a}z^k\\ &=\frac1{a!}\lim_{z\to 0}\sum_{k\ge a}f_k \Big( \prod_{i=0}^{a-1} (k-i) \Big)z^{k-a}\\ &=\frac1{a!}\lim_{z\to 0}\left(f_aa!+\sum_{k>a}f_k \Big( \prod_{i=0}^{a-1} (k-i) \Big) z^{k-a}\right)\\ &=f_n+\frac1{a!}\lim_{z\to 0}z\sum_{k\ge a+1}f_k \Big( \prod_{i=0}^{a-1} (k-i) \Big) z^{k-(a+1)}\ &=f_n\; \bullet \end{align*}$$

Answer 1

Here is the generalization they are probably looking for (with a few details left to be filled in):

Pseudo-theorem: Suppose that $f_n$ is a sequence defined by a recurrence relation with a generating function $g(z)$. Then if $g(z)$ satisfies certain properties (what properties are required to make the proof go through?), then one can derive an explicit formula for $f_n$ via $f_n + \sum_{z\neq 0} Res_z \frac{1}{z^{n+1}g(z)}=0$.

As a first attempt at figuring out what properties $g$ should satisfy, try seeing what is necessary if you assume that $g(z)$ is a rational function. Note that you will need to be a little more explicit about part (4) before you can get a satisfactory answer here. Also, if you assume that the denominator of $g$ only has simple roots, you should be able to come up with a rather explicit formula in terms of the factorization. For this, the following result (which you should try to prove; it uses nothing more than the product rule) is useful:

Lemma If $a$ is a simple root of a polynomial $p(z)$, then $\displaystyle \lim_{z\to a} \frac{p(z)}{(z-a)}=p'(a)$.

To see why this lemma is useful, try converting what you have so far for (4) into the Binet formula.

---

Edit: Adding an answer to the newly updated question (really, it's bad etiquette to continually change what you are asking in a question, as it makes previous answers look irrelevant).

The radius of convergence of a function $f(z)=\displaystyle\sum_{i\geq 0} a_i z^i$ is $\inf \{ \left| z \right| \mid z \in \mathbb C \text{ and } f \text{ has a pole/singularity at } z\}$. The statement can be found on wikipedia. It is easy to prove that the radius of convergence is at most this value, but proving the other direction requires a bit of complex analysis. The wikipedia page links to another artical which (in the remarks section) has a brief proof sketch.

Therefore, for a rational function, as long as the denominator is not a multiple of $z$, you have a non-zero radius of convergence.

---

There is a slightly subtler question to be asked with generating functions. Given a sequence $(f_n)$, you can always form the generating function $\sum f_n z^n$ as a formal power series, and if the sequence satisfies a recurrence relation, the generating function will often satisfy some sort of algebraic or differential equation, and in this case you can often use this equation to solve for the generating function (as you did in this problem). However, there is an important caveat. At least a priori, since the ring of formal power series is different from the ring of power series with non-zero radii of convergence is different from the ring of continuous/smooth functions defined on a neighborhood of $0$, there being a solution to in one of these places does not mean there is a solution in another, and even if there are, it doesn't mean they correspond.

To give an analogy, you can formally consider the sum $s=1+2+4+8+\ldots$, ignoring issues of convergence. Formally speaking $s=2s+1$ (because multiplying by 2 shifts very term over), and so if the sum converged to a number in $\mathbb R$, it would have to converge to $-1$, because that is the only solution to our constraining equation over $\mathbb R$. A sum of positive numbers can't be negative, though. The problem is that, to the extent which working formally with sums of this kind makes any sense, there are multiple solutions to the equation $s=2s+1$ when working formally.

The good news is that everything works out quite nicely for the n-Fibonacci numbers, or more generally for linear constant-coefficient recurrences (I think).