All Questions
15
questions
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$?
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
1
vote
1
answer
331
views
Is this graph theory proof correct?
Source
Question:
In this problem, we describe a faster algorithm, due to Hopcroft and Karp, for finding a maximum matching in a bipartite graph. The algorithm runs in O($\sqrt V E$) time. Given an ...
1
vote
1
answer
225
views
Alteration in Binary Strings Question
Question:
An alteration in a binary string is said to occur when the string encounters one of the following two patterns -
“01” or “10”.
For example, the string ...
user810551
0
votes
2
answers
115
views
Prove that the following proposition is true.
Let a ∈ Z and let b ∈ Z. If n does not divide ab then n does not divide a and n does not divide b.
I am currently studying discrete math and I am unsure of how to format this proof in such a way to ...
- 65
1
vote
1
answer
43
views
Prove, that the following rules for homomorphisms are true or false.
Let $\Sigma=\{a,b\}$, $L$ and $R$ be languages over $\Sigma$ and $h:\Sigma^* \to \Sigma^*$ be a homomorphism. Prove or disprove the following statements:
$h^{-1}(L\cup R)=h^{-1}(L)\cup h^{-1}(...
- 1,197
7
votes
1
answer
477
views
CheckMyProof: Proofs involving Big-O Notation
This is a homework exercise for a few weeks ago and I wanted your feedback on my improved proofs.
For $g: \mathbb{N} \to \mathbb{R}$ let
$$o(g):= \{f:\mathbb{N} \to \mathbb{R} |\forall \alpha >...
- 4,878
1
vote
0
answers
40
views
Determining the exact form and depth of a randomized search tree
I'm working on the following task and would like to know if I did it right:
Consider a randomized search tree with values
$x_i := \frac{i^2 - log_2(i)}{2}$ and the priorities $p_i := 256 -
>...
- 4,222
-1
votes
4
answers
1k
views
How to find which one that 3 divides: n, n+1 or 2n+1?
I've tried solving this equation for my assignment by replacing $n$ by any of the following possible integers
a number divisible by $3 (3k$)
$1 \mod 3 (3k+1)$
$2 \mod 3 (3k+2)$
However, I found ...
- 9
2
votes
0
answers
844
views
Discrete Mathematics: Prove Expression Is Even
I'm brushing up for my Discrete Math final exam, and would like to know if the following proof is valid...
Prove by direct proof that $a^2-5a+8$ is even for any integer $a$.
Proof: By factoring, we ...
- 121
1
vote
1
answer
1k
views
Prove : Independent set plus covering number is equivalent to number of vertices in a graph
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
AFAIK :
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are ...
- 4,785
0
votes
1
answer
936
views
Rewriting statements without using any quantifiers
Let $ P$ and $Q$ be predicates on the set $S$, where $S$ has three elements, say, $S = {a, b, c}$.
Then the statement $∀xP(x)$ can also be written in full detail as $P(a)∧P(b)∧P(c)$. Rewrite
each of ...
-1
votes
1
answer
453
views
Which of the following identities are true? Justify your answer - n! = O(4^n)..
Which of the following identities are true? Justify your answer
a)$n! = O(4^n)$
b)$4^n = O(n!)$
If I let $n = 0$ then $(0)! = O(4^0) \implies 1 = O(1)$ so this is true I think?
$4^n = O(n!)$
In ...
- 1,641
1
vote
4
answers
46k
views
Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.
Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then
$$
$$
(i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$)
$$
$$
(ii) if $a$ | $b$ then $a$|$bc$ for all integers $c$;
$$
$$
(iii) if $a$ |$b$ ...
- 1,641
0
votes
1
answer
2k
views
Rewriting statements with quantifiers to full detail
The question i have for an assignment is the following
Let P and Q be predicates on the set S, where S has two elements, say, S = {a, b}. Then the statement ∀xP(x) can also be written in full detail ...
- 115