满二叉树中节点高度之和的归纳证明
我试图通过归纳法证明以下内容：
sum(k*2^(H-k), k = 0 .. H) = N-H-1
这是算法类的问题。我在想我可以做我通常对求和所做的事情，即假设它适用于某些 P(m)，然后增加 P(m+1) 的总和并通过在右侧添加额外的内容来向后工作左侧求和产生。
但是，这个问题是不同的，因为替换 H+1 会改变求和中的每一项……所以我认为该技术行不通。
这是一个家庭作业问题......所以我显然不期待一个完整的解决方案。但是，我不太确定在哪里进行求和，所以我正在寻找其他进行归纳的方法。
I'm trying to prove the following by induction:
sum(k*2^(H-k), k = 0 .. H) = N-H-1
it's a problem for an algorithms class. I was thinking I could do what I normally do for summations, which is to assume that it works for some P(m) and then increment the sum for P(m+1) and work backwards by adding to the right side what the additional summation on the left side produces.
But, this problem is different because substituting H+1 changes each term inside of the summation... so I don't think that technique will work.
This is a homework problem... so I'm obviously not expecting a complete solution. But, I'm not really sure where to take the summation so I'm looking for other ways of doing the induction.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设树已满，您仍然可以通过归纳法进行一些传统的证明。只需写下，如果它适用于某个高度
H，那么您就知道该高度的高度总和为NH-1；然后尝试高度H+1。考虑一下：NH-1变成什么）？Assuming the tree is full, you can still do a somewhat traditional proof by induction. Just write that if it works for some height
H, then you know the sum of heights isN-H-1for that height; then try it for heightH+1. Consider:N-H-1become)?