1
$\begingroup$

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)

  • 0
    Sorry, only English :)2012-11-28

2 Answers 2

1

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

  • 0
    @dreamcrash: $\phi = \frac 12(1+\sqrt 5)$ which is in that interval2019-02-03
3

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.

  • 0
    @dreamcrash: If the recurrence relation without the trailing 1 has no known solution, there is little chance that, with the trailing 1, the relation would have a closed form solution.2012-11-29