Author |
Topic: the base case and step for induction proof (Read 1236 times) |
|
transgalactic
Newbie
Posts: 11
|
 |
the base case and step for induction proof
« on: Jan 15th, 2012, 1:31pm » |
 Quote  Modify
|
there is a binary tree which has
l1..lm leaves
and their depth are d1,..,dm
prove that
[TEX]\sum ^m_{i=1} 2^{-d_i}\leq1[/TEX]
there is a link to the foto of expression
http://i39.tinypic.com/1o3ep5.jpg
??
i have to prove it by induction
i found out that each node must have only 0 or 2 sons.
i dont know why??
i cant see what is the base cae here?
what is the inductive step here
?
|
| « Last Edit: Jan 15th, 2012, 1:33pm by transgalactic » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: the base case and step for induction pro
« Reply #1 on: Jan 15th, 2012, 10:05pm » |
Quote Modify
|
on Jan 15th, 2012, 1:31pm, transgalactic wrote:
i found out that each node must have only 0 or 2 sons.
i dont know why?? |
|
Because it's a binary tree.
Quote:| i cant see what is the base cae here? |
|
Base case is a tree composed of a single leaf.
Quote:| what is the inductive step here |
|
Given the formula holds for all binary trees of depth D-1, prove it holds for a binary tree of depth D
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print