0
$\begingroup$

I admit I'm little bit poor in functions in mathematics. But I'm in real urge to get this riddle out.

How to express $x(n)=x(n-1)+x(n-2)+1,$ where $n>1$ and $x(0)=0$ and $x(1)=1$, in terms of the function $y(n)=y(n-1)+n,$ where $n>1$ and $y(0)=0$ and $y(1)=1$?

I found the answer as $x(n)=y(n+2)-1$ in a some PDF about AVL trees for the minimal number of nodes $n_{\min}(h)$ of an AVL tree of height $h$.

Please explain.

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/3922/discussion-between-cdummy-and-brian-m-scott)2012-06-28

1 Answers 1

1

The Fibonacci numbers are defined by $f_0=0,f_1=1$, and $f_n=f_{n-1}+f_{n-2}$ for $n>1$. Your sequence $x$ is defined by $x_0=0,x_1=1$, and $x_n=x_{n-1}+x_{n-2}+1$ for $n>1$. We wish to prove that $x_n=f_{n+2}-1$ for $n\ge 0$.

We first observe that $x_0=0=1-1=f_2-1$ and $x_1=1=2-1=f_3-1$; this gets the induction off the ground.

Now for the induction step let $n>1$ be arbitrary, and assume as the induction hypothesis that $x_k=f_{k+2}-1$ for $k=0,\dots,n-1$. Then

$\begin{align*} x_n&=x_{n-1}+x_{n-2}+1\tag{1}\\ &=\Big(f_{(n-1)+2}-1\Big)+\Big(f_{(n-2)+2}-1\Big)+1\tag{2}\\ &=f_{n+1}+f_n-1\tag{3}\\ &=f_{n+2}-1\tag{4}\;, \end{align*}$

where $(1)$ follows from the definition of the $x$’s, $(2)$ from the induction hypothesis, $(3)$ by elementary arithmetic, and $(4)$ from the definition of the Fibonacci numbers.

The result now follows by induction: we’ve shown that it’s true for $n=0$ and $n=1$, and we’ve shown that if it’s true for all non-negative $k, then it’s true for all $k.

  • 0
    M.Scott Thanks dude2012-06-28