All Questions
23
questions
2
votes
0
answers
76
views
the Ackermann function must be total and unique based on one specific list of rules
This is one following question based on one question I asked before.
In mcs.pdf, it has Problem 7.25 in p251(#259).
One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
- 416
0
votes
1
answer
84
views
partial function version of the Ackermann function must be total
In mcs.pdf, it has Problem 7.25. (I only solve somewhat important problems referred to in the chapter contents because I have learnt one Discrete Mathematics book before and read mcs to ensure no ...
- 416
1
vote
1
answer
193
views
Lambda Calculus: Proving exponent property by induction
Recently I have learned that given Church numerals $\bar n = \lambda fx.f^n x$ and $\bar m = \lambda fx.f^m x$, we can calculate $\overline{m^n}$ by applying $\exp=\lambda mn.nm$. I believe this means ...
- 23
0
votes
0
answers
303
views
Prove that MergeSort is stable for any input size n ∈ N using induction on n.
In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
1
vote
1
answer
601
views
How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?
I have been asked this question in an assignment for my exam.
The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. ...
- 13
0
votes
0
answers
43
views
Induction proof - Logic
How can you go from $(k+1)k!>(k+1)2^k$ to $(k+1)!>(k+1)2^k$ in induction?
(Assumption: $k!>2^k), k>4$
Why can the LHS get rid of the $k$?
3
votes
1
answer
244
views
Proving terms using induction in LC
Expanding on the following question here and on the book on the $\lambda$-calculus I'm reading, I'm trying to prove the correctness of the given solution in a more complicated manner.
Let $(F_n')_{n \...
- 125
2
votes
1
answer
870
views
Lambda calculus - church encoding and lists
I'm reading a book on the $\lambda$-calculus and I'm stuck on a list of representations. While practising different lambda calculus tasks I've stumbled upon an interesting issue. Given two terms I ...
- 125
1
vote
1
answer
49
views
Counterexample to a recursive matched parenthesis proposition.
I am attempting problem 7.28 of Discrete Mathematics notes from MIT OCW. Link to problem
Definitions: All recursively defined
RecMatch (RM):
Base Case: $\lambda \in RM$ [$\lambda$ is empty string]
...
1
vote
1
answer
209
views
Prove that $\operatorname{ack}(3,y)=2^{y+3}-3$.
Prove that:
$$\operatorname{ack}(3,y)=2^{y+3}-3$$
where $\operatorname{ack}$ refers to the Ackermann function.
Here's what I have so far.
This statement can be prove by induction over $y$.
Induction ...
- 1,928
0
votes
0
answers
47
views
Prove the number of expected nodes in a Binary Tree using Mathematical Induction.
The following random process constructs a Binary Search Tree:
...
- 176
0
votes
0
answers
30
views
Find minimum $x$ such that for all $y\geq x$, a combination of cents exists that adds upto $y$. ($p_1$ to $p_n$ denominations of cents available).
Given cents of value $p_1,p_2,p_3,\cdots ,p_n$. Aim is to find minimum value of $x$ such that for all $y>=x$, there exists a combination of given cents denomination that adds upto $y$.
All $p_i$'s ...
1
vote
1
answer
375
views
Prove that RecMatch is closed under string concatenation - Structural Induction
Let RecMatch be the set of strings of matched brackets of Definition 7.2.1. Prove that RecMatch is closed under string concatenation via structural induction. Namely, if s and t are strings in ...
- 39
0
votes
1
answer
386
views
Induction proof of derivation of string
I have the following Context free grammar where:
S → SS
S → hSm
S → ε
and the question I'm answering is:
"Prove by induction on n,that for all n ≥ 0, the string ...
- 189
0
votes
2
answers
445
views
Prove a relation to be reflexive by induction
Base case ~: For all $s,s' \in S$
$$treeS \sim treeS'$$
Step case ~: for $ t \sim t', t'' \sim t'''$ and $s,s' \in S$
$$tree_s(t,t') \sim tree_{s'}(t'',t''')$$
I was able to understand what ...
- 159