代码之家 › 专栏 › 技术社区 › Alex Mullans

全二叉树节点高度和的归纳证明

proof tree

Alex Mullans · 技术社区 · 14 年前

我想通过归纳法来证明以下几点:

sum(k*2^(H-k), k = 0 .. H) = N-H-1

但是,这个问题是不同的,因为替换H+1会改变求和中的每个项。。。所以我认为这种技术行不通。

这是一个家庭作业问题。。。所以我显然不期待一个完整的解决方案。但是,我不太确定在哪里求和,所以我在寻找其他的归纳方法。

1 回复 | 直到 14 年前

Tim 14 年前

假设树是满的,您仍然可以通过归纳来做一些传统的证明。只要写下如果它能达到一定高度 H ,那么你知道高度之和是 N-H-1 H+1 . 考虑:

推荐文章

Fellixxxxxxxxxxx · 证明大O符号语句

7 年前

CMCDragonkai · Haskell:函数应用程序在列表连接上分布是真的吗?

9 年前

Peach · 如何证明这种贪婪算法的最优性?

9 年前

Albtzrly · 如果(and b b c=orb b c)在coq中,我如何证明b=c?

9 年前

user2303325 · 通过证明递归是Omega(nlogn)来归纳证明递归不是O(n)

9 年前

Yury · 数学证明助手

10 年前

Olle Härstedt · 经验证的正确收据模块

11 年前

amorimluc · 如何演绎地证明以下逻辑陈述?[已关闭]

12 年前