7
$\begingroup$

Given the Fibonacci, tribonacci, and tetranacci numbers,

$$F_n = 0,1,1,2,3,5,8\dots$$

$$T_n = 0, 1, 1, 2, 4, 7, 13, 24,\dots$$

$$U_n = 0, 1, 1, 2, 4, 8, 15, 29, \dots$$

and so on, how do we show that,

$$\sum_{n=0}^{\infty}\frac{F_n}{10^n} = \frac{10}{89}$$

$$\sum_{n=0}^{\infty}\frac{T_n}{10^n} = \frac{100}{889}$$

$$\sum_{n=0}^{\infty}\frac{U_n}{10^n} = \frac{1000}{8889}$$

or, in general,

$$\sum_{n=0}^{\infty}\frac{S_n}{p^n} = \frac{(1-p)p^{k-1}}{(2-p)p^k-1}$$

where the above were just the cases $k=2,3,4$, and $p=10$?

P.S. Related post.

$\endgroup$
  • $\begingroup$ Have you tried to find explicit formulas for $S_n$ like Binet's? $\endgroup$ – Michael Galuza Jul 17 '15 at 3:51
  • $\begingroup$ @MichaelGaluza: Yes, actually. If you look at the general formula (eq.5) at mathworld.wolfram.com/Fibonaccin-StepNumber.html, I gave that to Eric back in 2005. But I just found that empirically. $\endgroup$ – Tito Piezas III Jul 17 '15 at 4:00
  • 1
    $\begingroup$ I might be overlooking something, but I believe that something similar to Thomas Andrew's solution to your other question (generating functions) should give you the value, while convergence might be proven by showing $S_n/p^n < 1$ for sufficiently large $p$. (I haven't actually followed this path of reasoning out, but it "feels right." If I follow through it through, I'll leave a comment or answer explaining how it turned out.) $\endgroup$ – apnorton Jul 17 '15 at 4:04
  • $\begingroup$ By $S_n$ do you mean $S_i = F_i$ for $i < n$ and $S_i = S_{i-1} + \ldots + S_{i -n}$? $\endgroup$ – Marcus M Jul 17 '15 at 4:05
  • $\begingroup$ @MarcusM I believe the standard definition is $S_i = 0$ for $i \leq 0$, $S_1=1$, and $S_i = S_{i-1} + \cdots + S_{i-k}$. $\endgroup$ – apnorton Jul 17 '15 at 4:07
2
$\begingroup$

Outline: This follows the spirit of Thomas Andrew's solution to the OP's other question to find the value of the series. Convergence is then proven by showing $S_n/p^n<1$ for sufficiently large p.


Finding the Value with Generating Functions:

Define $S_n$ for a fixed $k$ as follows: $$S_n = \begin{cases} 0 & n \leq 0 \\ 1 & n = 1 \\ \sum_{j=1}^k S_{n-j} & n > 1 \end{cases}$$ Let $\mathcal{S}(z) = \sum_{n\geq 0}S_nz^n$. I assert without proof (I'll seek a source paper, rather than derive it myself) that: $$\mathcal{S}(z) = \frac{z}{1 - z - z^2 -\dots - z^k}$$

It follows: \begin{align*} \mathcal{S}(z) &= \frac{z}{1 - z - z^2 -\dots - z^k} \\ &= \frac{z}{2 - \sum_{j=0}^k z^j} \\ &= \frac{z}{2 - \frac{z^{k+1}-1}{z-1}} \\ &= \frac{z(z-1)}{2z -z^{k+1}-1} \\ &= \frac{z(z-1)}{(2-z^k)z-1} \end{align*}

The value we seek is $\mathcal{S}(1/p)$: \begin{align*} \mathcal{S}(1/p) &= \frac{(1/p)\left(\frac{1}{p}-1\right)}{\left(2-\frac{1}{p^k}\right)\frac{1}{p}-1} \\ &= \frac{\frac{1-p}{p^2}}{\left(\frac{2p^k-1}{p^{k+1}}\right)-1} \\ &= \frac{1-p}{\frac{p^2}{p^{k+1}}\left(2p^k-1 -p^{k+1}\right)} \\ &= \frac{(1-p)p^{k-1}}{(2-p)p^k -1} \end{align*}

This is as desired.


Proving Convergence:

However, this only provides the value if the series converges; that proof is entirely separate.

It is generally known that $S_n \in \mathcal O( r^n )$, where $r$ is the largest real root of the equation $2-\sum_{j=0}^k z^j = 0$. To justify this, consider the last identity in this Wiki article and consider its asymptotic behavior. (I don't like the source of that, but I'll find a better one later).

Thus, so long as $r < p$, the series $\mathcal{S}(1/p)$ is bounded above by a convergent geometric series $\sum_{n\geq 0} \left(\frac{r}{p}\right)^n$.

Fortunately, based on Lemma 2.7 of this arxiv paper, we know that the largest real root of $2-\sum_{j=0}^kz^j = 0$ is strictly bounded between $1$ and $2$. Thus, so long as $p \geq 2$, we have convergence.

$\endgroup$
  • 1
    $\begingroup$ Your assertion on the generating function is very easy to prove, not worth hunting a reference for; just compute $S(z)-(zS(z)+z^2S(z)+\cdots+z^kS(z))$ term-by-term, using the generating relation for $n\gt k$ and the explicit definition for $n\leq k$. $\endgroup$ – Steven Stadnicki Jul 17 '15 at 19:07
2
$\begingroup$

The difference equations given by the suggested series are: \begin{align} F_{n+2} &= F_{n+1} + F_{n} \\ T_{n+3} &= T_{n+2} + T_{n+1} + T_{n} \\ \tag{1} U_{n+4} &= U_{n+3} + U_{n+2} + U_{n+1} + U_{n} \end{align} and so on. In general they take on the form \begin{align}\tag{2} \phi_{n+m} = \sum_{k=0}^{m-1} \phi_{n+m-k-1}, \end{align} where $\phi_{0}, \phi_{1}, \phi_{2}, \cdots $ are the initial values. By considering the generating function defined by \begin{align} f_{m}(t) = \sum_{n=0}^{\infty} \phi_{n+m} \, t^{n} \end{align} then it is readily found that \begin{align} f_{m}(t) &= \frac{1}{ 2 - \sum_{k=0}^{m} t^{k}} \cdot \sum_{k=0}^{m-1} \left[\left( \phi_{k} - \sum_{s=0}^{k-1} \phi_{s} \right) \, t^{k} \right] \\ &= \frac{1 - t}{1 - 2 t + t^{m+1}} \, \cdot \sum_{k=0}^{m-1} \left[\left( \phi_{k} - \sum_{s=0}^{k-1} \phi_{s} \right) \, t^{k} \right] \tag{3} \end{align} if $t \to 1/t$ then \begin{align} f_{m}(t) &= \frac{t^{m} (t - 1)}{1 - 2 t + t^{m+1}} \, \cdot \sum_{k=0}^{m-1} \left[\left( \phi_{k} - \sum_{s=0}^{k-1} \phi_{s} \right) \, \frac{1}{t^{k}} \right] \end{align} When $t = 10$ this reduces to \begin{align}\tag{4} f_{m}\left(\frac{1}{10}\right) = \frac{9}{(10)^{m+1}- 2 \, (10)^{m} + 1} \cdot \sum_{k=0}^{m-1} \left[\left( \phi_{k} - \sum_{s=0}^{k-1} \phi_{s} \right) \, (10)^{m-k} \right] \end{align}

As an example let $m=3$, which corresponds to the Tribonacci series, to obtain \begin{align} f_{3}\left(\frac{1}{10}\right) &= \sum_{n=0}^{\infty} \frac{T_{n}}{(10)^{n}} = \frac{9 \, (10)^{3}}{10^{4} - 2 \cdot 10^{3} + 1} \cdot \left(\frac{1}{10}\right) = \frac{100}{889}. \end{align}

$\endgroup$
  • $\begingroup$ Although this gives the form requested, it does not technically prove the series converges; that must be done separately. But, +1 even so. $\endgroup$ – apnorton Jul 17 '15 at 4:41
0
$\begingroup$

That's because $\sum_{n=0}^{\infty} F_nx^n =\frac1{1-x-x^2} $.

Putting $x = \frac1{10^k}$ gives $\sum_{n=0}^{\infty} \frac{F_n}{10^{kn}} =\frac1{1-10^{-k}-10^{-2k}} =\frac{10^{2k}}{10^{2k}-10^{k}-1} $.

For the others, the generating function is $\sum_{n=0}^{\infty} G_n x^n =\frac1{1-x-x^2-...-x^m} $ where $m=2$ for Fib, $m=3$ for Trib, and $m=4$ for Tetra.

For each of these, $\sum_{n=0}^{\infty} \frac{G_n}{ 10^n} =\frac1{1-\frac1{10}-\frac1{100}-...-\frac1{10^{m}}} =\frac{10^m}{10^m-10^{m-1}-...-1} =\frac{10^m}{8...(m-1 \ 8s)9} $.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.