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
    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$.2012-06-28
  • 0
    @BrianM.Scott could you explain how to get this in the other way around2012-06-28
  • 0
    @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) -12012-06-28
  • 0
    @BrianM.Scott sorry i mistyped it is x(n) = y(n+2) - 1. Please check it now2012-06-28
  • 0
    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.2012-06-28
  • 0
    @BrianM.Scott please check the comment i put fib and nmin functions instead of x and y2012-06-28
  • 0
    I have no idea what *nmin* is.2012-06-28
  • 0
    @BrianM.Scott nmin(0) = 0 nmin(1) = 1 nmin(h) = 1 + nmin(h -1) + nmin(h -2), when h >1 its a function2012-06-28
  • 0
    Ah. That’s true enough, and easily proved by induction on $n$. Are you asking for a proof?2012-06-28
  • 0
    @BrianM.Scott yes i need that2012-06-28
  • 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