# Algorithms and generalisation of functions

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$.

-
If you calculate a few values of both sequences, you’ll quickly find that it’s not true that $x(n)=y(n+2)+1$. –  Brian M. Scott Jun 28 '12 at 21:14
@BrianM.Scott could you explain how to get this in the other way around –  cdummy Jun 28 '12 at 21:16
@BrianM.Scott nmin(0) = 0 nmin(1) = 1 nmin(h) = 1 + nmin(h -1) + nmin(h -2), when h >1 Compare this with the Fibonacci series: Hence: nmin(h) = fib(h +2) -1 –  cdummy Jun 28 '12 at 21:18
@BrianM.Scott sorry i mistyped it is x(n) = y(n+2) - 1. Please check it now –  cdummy Jun 28 '12 at 21:23
Your $x$ sequence is $0,1,2,4,7,12,20,33,\dots$; your $y$ sequence is $0,1,3,6,10,15,21,28,\dots$. Neither is an offset of the other. –  Brian M. Scott Jun 28 '12 at 21:24

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<n$, then it’s true for all $k<n+1$.

-
M.Scott Thanks dude –  cdummy Jun 28 '12 at 21:50