Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
M.Scott Thanks dude –  cdummy Jun 28 '12 at 21:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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