algorithm - ⌈lg(n+1)⌉=⌊lgn⌋+1 地板和天花板证明

Question

我有作业问题，要求证明其中一个天花板属性。⌈lg(n+1)⌉=⌊lgn⌋+1

我试图证明使用归纳技术。1. n = 1 值，我们在两边都得到值 1。2. 我们假设 n = k 3. 我们必须证明 n = k+1

我被困在这里，如何证明这第三步。有没有其他方法可以证明相同？我知道这是作业问题。不回答，但一些提示将不胜感激。

Answer 1

假设 lg 是 log10。对于任何 n，其中 10^k <= n < 10^(k+1) - 1 对于某个整数 k。k < lg(n+1)< k+1，即⌈lg(n+1)⌉ = k+1，k =< lgn < k+1，则⌊lgn⌋+1 = k+1。等式将是正确的。那么，我们只需要特别处理n=10^(k+1)-1的情况，当n= 10^(k+1)-1, lg(n+1) = k+1, k < lgn < k+1，即⌊lgn⌋+1 = k+1。最重要的是，对于任何整数 n，⌈lg(n+1)⌉=⌊lgn⌋+1 始终为真。

Answer 2

我可以证明它是假的。如果lg是 log ₁₀并且n是 99.5，那么ceil(lg(99.5+1))是 3floor(lg(99.5))+1而是 2，你的等式不成立。