2
$\begingroup$

I have to show the following:

Let $N_k=\frac{p_k}{q_k}$ with $\alpha=\langle 1;2,3,4,...,n,n+1\rangle$ and $n \in \mathbb{N}$. Then $\forall n \in \mathbb{N}$ with $n\geq 3$,

$p_n=n(p_{n-1}+p_{n-2})+(n-1)p_{n-3}+(n-2)p_{n-4}+\dots+3p_1+2p_0+2\;.$

$p_n$ is the n-th numerator of the convergent of $\alpha$ and $\alpha$ is a continued fraction, the number before the ";" is the part of the continued fraction in front of the "real" fraction, for example $\langle a;b,c\rangle =a+\frac{1}{b+\frac{1}{c}}$

As hint I got "Use Induction", but I don't know where to start.

I suggest:

$n=3 \rightarrow p(3)=3(p_2+p_1)+2p_0+2=3p_2+3p_1+2p_0+2$

Now I have to find out $p(3)$, so I have to get the continued fraction $\alpha=\langle 1;2,3\rangle$, but I don't know how to get my $\frac{p_k}{q_k}$.

Any hints would be helpful.

  • 2
    $\LaTeX$ tip: don't use `<` and `>` as delimiters; they are operation symbols, so there is extra white space added to both sides, and the spacing comes out wrong. The corresponding delimiters are `\langle` and `\rangle`, as Brian Scott's edit of your question showed.2011-11-25

1 Answers 1

2

To get you started:

The successive convergents of $\langle 1;2,3\rangle$ are $\langle 1\rangle = \frac11$, $\langle 1;2\rangle = \frac32$, and $\langle 1;2,3\rangle = 1+\frac1{2+\frac13}=1+\frac1{7/3}=$ $1+\frac37=\frac{10}3$, so $p_0=1$, $p_1=3$, and $p_2=10$. Thus, $3p_2+3p_1+2p_0+2=43$. And $\langle 1;2,3,4\rangle =$ $1+\frac1{2+\frac1{3+\frac14}}=1+\frac1{2+\frac4{13}}=1+\frac{13}{30}=\frac{43}{30}$, so $p_3$ is indeed $43$.

You might want to look at this material for information on how the convergents are calculated recursively.

Added: Your continued fraction is $\langle a_0;a_1,a_2,\dots\rangle$, where $a_n=n+1$. Thus, the recurrence given in the Wikipedia article becomes $p_n=(n+1)p_{n-1}+p_{n-2}$, or $p_{n+1}=(n+2)p_n+p_{n-1}$. Assume as an induction hypothesis that

$p_n=n(p_{n-1}+p_{n-2})+(n-1)p_{n-3}+(n-2)p_{n-4}+\dots+3p_1+2p_0+2$ and $p_{n-1}=(n-1)(p_{n-2}+p_{n-3})+(n-2)p_{n-4}+(n-3)p_{n-5}+\dots+3p_1+2p_0+2\;.$ Then $\begin{align*} p_{n+1}&=(n+2)p_n+p_{n-1}\\ &=(n+1)p_n+p_n+p_{n-1}\\ &=(n+1)p_n+\left(np_{n-1}+\sum_{k=0}^{n-2}(k+2)p_k+2\right)+p_{n-1}\\ &=(n+1)(p_n+p_{n-1})+\sum_{k=0}^{n-2}(k+2)p_k+2\;, \end{align*}$

which is exactly what you need it to be for the induction to go through.

  • 0
    Thanks for the start, now I continue with $p_{k+1}=a_{k+1}p_k+p_{k-1}$ (from the wiki)? But I don't see, where to use in $p_{k+1}=a_{k+1}p_k+p_{k-1}$ my "induction hypothesis" $(p_n)$. Do I replace it with $p_n=n(p_{n-1}+p_{n-2})+(n-1)p_{n-3}+(n-2)p_{n-4}+...$?2011-11-26