0
votes
1answer
126 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
2
votes
3answers
44 views

Strong Induction, assuming k<n where k and n are not numbers

In strong Induction for the induction hypothesis you assume for all K, p(k) for k If for example I am working with trees and not natural numbers can I still use this style of proof? For example if I ...
0
votes
0answers
26 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
3
votes
1answer
126 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
3
votes
2answers
88 views

Proving that $xy = yx$ where $x$ and $y$ are both strings.

I am to prove that the following holds for any two strings $x, y \in \lbrace 0, 1\rbrace^*$ $xy = yx$ if and only if $\exists z \in \{0,1\}^*$ and $i,j \in \mathbb N$, such that $x = z^i$ and $y = ...
2
votes
0answers
45 views

Induction Problem ($n^2 ≤ 2^n$) [duplicate]

So I have this induction problem: $$n^2 ≤ 2^n \;\text{ for } \; n ≥ 4$$ I know the base case is ($n=4$) which checks out. I know the hyp is ($n=k$) giving $k^2 ≤ 2^k$. However, I am getting ...
1
vote
1answer
518 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
58 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
163 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
1k 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
682 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
598 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 ...