# Recurrence T(n) = T(n-1) + T (n/2) + 1

I am try to find the solution to the recurrence T(n) = T (n-1) + T(n/2) + 1

Whats I have done:

T(n) = 2T(n-1 + n/2) + 1
T(n) = 2T(2n/2 - 2/2 + n/2) +1
T(n) = 2 T((3n - 1)/2) +1

if U(X) = T(x/3 + 1) then:

U(X) = 2U(x/2)
U(X) = x

T(n) = 3(N  - 1) + 1


This makes any sense ?

Edit: The context is computer science, so when you divide n/2 and n odd you get the next inferior natural number (e.g 1/2 -> 0)

• No, it doesn't. What's the solution you got? Did you try it? Does it work? – Patrick Da Silva Nov 28 '12 at 0:59
• I try on T(4) it gives me 9 I think it suppose to be 8. Yes I did try, not every one is an expert in mathematic. – dreamcrash Nov 28 '12 at 1:07
• Hmm, I don't understand the recurrence relation itself. What is meant by $T(n/2)$ when $n$ is odd? – user1551 Nov 28 '12 at 1:21
• @PatrickDaSilva I should had added to the question. – dreamcrash Nov 28 '12 at 1:27
• A couple simple estimates... If $T(1) \geq 0$ then $T(n) \geq 0$ for all $n$ and thus $T(n) \geq T(n-1)$ for all $n$. This gives $$T(n) \geq 2T(\lfloor n/2 \rfloor) \geq 2^{\lfloor \log_2 n \rfloor} T(1)$$ and $$T(n) \leq 2 T(n-1) \leq 2^{n-1} T(1).$$ Based on the plot of the values of $T(n)$, it looks like $T(n)$ has superlinear growth. – Antonio Vargas Nov 28 '12 at 3:22

This series is shown in OEIS. It clearly grows more slowly than the Fibonacci numbers, as you increment by smaller values. This shows $T(n) \in o(\phi ^n)$.
• @dreamcrash: $\phi = \frac 12(1+\sqrt 5)$ which is in that interval – Ross Millikan Dec 2 '12 at 3:37
Your first line, $$T(n) = 2T(n-1 + n/2),$$ is already nonsensical. The problems are twofold. First, $T$ is not guaranteed to be additive, so $T(n-1)+T(n/2)$ (the RHS of the original recurrence relation) is not necessarily equal to $T(n-1 + n/2)$. Second, even if $T$ is additive, what you get should be $T(n) = T(n-1) + T(n/2) = T(n-1 + n/2)$, but for some curious reason, you further throw in a multiplicative factor of $2$ to get $T(n) = 2T(n-1 + n/2)$.
At any rate, the sequence generated by the recurrence relation $T(n)=T(n-1)+T(\lfloor n/2\rfloor)$ has been indexed as A033485 in OEIS. According to OEIS, when $T(1)=1$, the sequence "gives the number of partitions of 2n into 'strongly decreasing' parts". Apparently no closed form solution for $T(n)$ is known.