Algorithms and generalisation of functions [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

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 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 nmin(n) of an AVL tree of height n.

Please explain.

Answer 1

Please be more clear about what you actually want and why (if that's relevant).

Your first equation is not homogeneous. To make it homogeneous you can write it in this form:

x[n]+1 = (x[n-1]+1)+(x[n-2]+1)

and substitute u[n] = x[n] + 1 to get

u[n] = u[n-1]+u[n-2] with u[0] = 1, u[1]=2.

These numbers are known as Fibonacci Numbers. There are several formulas and results regarding these numbers. For example

u[n-2] = (phi^n - (-phi)^(-n)) / sqrt5 with phi = (1 + sqrt 5) / 2 = 1.618...

which gives a formula for x[n] in your original equation:

(phi^(n+2) - (-phi)^(-n-2)) / sqrt5 - 1

On the other hand, your other equation y[n] = y[n-1] + n can be reiterated as

y[n] = y[n-1] + n = y[n-2] + (n-1) + n = ... = 1 + 2 + ... + n

It is well known that this sum is y[n] = n(n+1)/2

I see no obvious relation between x[n] and y[n] as you provided.