戎解证明题2：求解递推方程并证明结论 证明T(n)=T（[n/2]）+1的解是O(logn）(注：不能直接使用 主定理）。

我们可以通过数学归纳法来证明递推方程T(n) = T([n/2]) + 1的解是O(logn)。

首先，我们需要证明基本情况，即 n = 1 时，T(n) = T(0) + 1 = 1，因此，结论成立。

接下来，我们假设对于所有的 k < n，结论都成立，即 T(k) ≤ clogk，其中 c 是一个常数。我们需要证明当 n 时，结论也成立，即 T(n) ≤ clogn。

根据递推式，我们有T(n) = T([n/2]) + 1。由于 [n/2] ≤ n/2，根据归纳假设，我们有 T([n/2]) ≤ clog(n/2)。因此，T(n) ≤ clog(n/2) + 1 = clogn - clog2 + 1。由于 log2 = 1，我们得到 T(n) ≤ clogn。

因此，根据数学归纳法，我们证明了递推方程T(n) = T([n/2]) + 1的解是O(logn)。