Tagged Questions

1
vote
1answer
88 views

Using mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes

Use mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes. I'm familiar with mathematical induction proofs, but I haven't encountered one like this. ...
0
votes
3answers
45 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
2
votes
1answer
91 views

Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
2
votes
2answers
235 views

meaning of 'Hypothesis' in simple terms?

could anyone please clarify me the meaning of the term 'hypothesis'? with relation to terms 'reasoning' and 'assumption' ? Many thanks
3
votes
2answers
561 views

Proving insertion sort using induction

A while back when I was taking a first year cs course, our professor had us write the algorithm for insertion sort in The Scheme programming language. There were also several other similar recursion ...
3
votes
3answers
2k views

Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$: $$ |xy| = |x| + |y| $$ with $x, y \in \Sigma^*$. To ...
6
votes
1answer
517 views

Proof by double induction on strings (SOLVED)

I am truly baffled as to go on to prove this by double induction: http://i.stack.imgur.com/Zvrzt.png (snap shot of question) This question seems rather trivial on first glimpse, however trying ...