如何求解遞推式 T(n) = T(n-1) + T(floor(n/2)) + 1？

01-06

完整的遞推式為 $T(n) = T(n-1) + T(lfloor n/2 floor) + 1$ 。
初值為 $T(0) = 1, T(1) = 3, T(2) = 5, T(3) = 7$ ，遞推式從 $n=4$ 開始有效。
這個遞推式超出了Master theorem和Akra-Bazzi method能夠處理的範圍。
用z變換求解也遇到了困難（式中同時出現了 $mathcal{T}(z)$ 和 $mathcal{T}(z^2)$ ）。

在知乎上搜索也沒有發現本質相同的遞推式。
感覺跟下面這個函數有相似之處：
請問形狀如下圖的函數，且滿足f "(x) = f(2x)。如何得到這個函數的具體形式？ - 數學
如果求完整表達式很困難，能求出Big-Theta notation也可以。

目測 $T(n)=e^{(frac{1}{2}+o(1))log^2 n}$ ，是quasi-polynomial。

***********以下是更新***********

$T(n)-T(n-1)=T$ 對於某個 $0leq xileq 1$ 。鑒於我們只是在目測答案，所以捨棄這個 $xi$ 。於是，就是要求某個 $T$ 使得 $T$ 。

開始目測：代任何一個polynomial $T(n)=n^c$ ，發現右邊太大，說明 $T(n)$ 是super-polynomial。代 $T(n)=e^{cn}$ ，發現左邊太大，說明 $T(n)$ 是sub-exponential。於是，(不知道為什麼)設 $T(n)=e^{f(log n)}$ ，即 $e^{f(log n)}f$ 。兩邊取對數，換元，再用之前的trick，得到 $f$ 。於是， $f(t)approx frac{1}{2} t^2$ 。

最後，將 $T(n)=e^{clog^2 n}$ 代入原遞歸式驗算，發現 $c<frac{1}{2}$ 時，右邊大， $c>frac{1}{2}$ 時，左邊大。就可以用歸納法證明 $T(n)=e^{(frac{1}{2}+o(1))log^2 n}$ 了(？)

具體求解特別困難的樣子。漸進的話如下勉強可作（弊）。（剛發現你的初始值居然不太一樣，不過應該不影響結果...）

首先生成前若干項(Mathematica):

{1, 3, 5, 9, 13, 19, 25, 35, 45, 59, 73, 93, 113, 139, 165, 201, 237, 283, 329, 389}

丟到OEIS里，得到這個序列：A102378 - OEIS。（設為 $a(n)$ ）

裡面寫了 $a(n) - a(n-1) = ext{A018819}(n+1)$ ，所以跑到A018819看下描述（把 $n$ 拆分成2的冪的和的方法數，設為 $p(n)$ ）。

然後隨便Google搜搜partitions into powers of two之類的，找到A000123 - OEIS （把 $2n$ 拆分成2的冪的和的方法數，即 $p(2n)$ ）。

裡面Formula里，解析組合學的鼻祖之一的Philippe Flajolet（同時也是我最近看的書的作者之一，可惜已逝）提到漸進展開已在de Bruijn的論文里給出。

在同頁面查找de Bruijn，找到論文名《On Mahler"s partition problem》及其PDF http://www.dwc.knaw.nl/DL/publications/PU00018536.pdf

點開鏈接，得到A000123（把2n拆分成2的冪的和的方法數）的漸進表達式。忽略低階項和係數， $p(2n)sim exp(log(n)^2)sim p(n)$ 。

回到一開始，因為 $p(n) le a(n) le np(n) sim exp(log(n)) cdot exp(log(n)^2) sim exp(log(n)^2) sim p(n)$

所以夾逼得到 $T(n)=a(n)sim exp(log(n)^2)$ 。

省略了n多係數/低階項，也有若干的off by 1（懶），不過但願漸進階不差太多...感興趣的可以嚴格分析一下，把log的係數什麼的補上。

考慮 $x ightarrow +infty$ 時滿足 $T$ 的函數 $T(x)$ ，有

$T(x)=exp{(frac{{(ln{x})}^{2}}{2ln{2}}-frac{ln{x}ln{ln{x}}}{ln{2}}+(-frac{1}{2}+frac{1}{ln{2}}+frac{ln{ln{2}}}{ln{2}})ln{x}+frac{(ln{ln{x}})^{2}}{2ln{2}}+(-1+frac{ln{ln{2}}}{ln{2}})ln{ln{x}}+O(1))}$

計算可能有誤。

原遞推式不太懂，不過個人猜想 $T[n]=kT(n)(1+o(1))$ 。