擅长:python、mysql、java
<blockquote>
<p>is there a more intuitive way to explain why its 2^n?</p>
</blockquote>
<p>首先,它不是<code>2^n</code>。它确实是指数型的,是n次方的,但这不一定是2</p>
<p>一点数学知识:任何线性递归关系都允许以<code>T(n) = a ** n</code>形式的解,在这种情况下<code>a</code>是特征多项式的根</p>
<pre><code>a ** D = a ** {D-1} + a ** {D-2} + ... + 1
</code></pre>
<p>现在你需要证明的是有一个大于1的根,这或多或少是微不足道的。事实上,当<code>a</code>等于1时,左侧(即1)小于右侧(即<code>D</code>)。当<code>a</code>增长到无穷大时,LHS的增长速度比RHS快,并最终变得更大。这意味着存在<code>a > 1</code>,在这一点上它们是相等的</p>
<p>差不多就是这样。我的数学老师想多听一点。作为一名面试官,我会很高兴的</p>