Tagged Questions

2
votes
3answers
55 views

Set Distributive Property Proof

Prove the distributive property for sets: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ I'm not good with proofs but my understanding is that I have to prove 2 things: (1) $A \cup (B ...
-2
votes
1answer
52 views

Given the following recurrence relation, prove using mathematical induction

How can we prove this using mathematical induction? $m_1 = 0$ $m_k = m_{\lfloor (k/2) \rfloor} + m_{\lceil (k/2) \rceil} + k-1$ for all integers $k \geq 1$ Prove using mathematical induction that ...
0
votes
6answers
111 views

Finding the number of subsets of S

How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6? Thanks!
0
votes
2answers
49 views

Use the binomial theorem to expand

How can we expand this using the binomial theorem? $(x^2 + 1/x)^7$
2
votes
3answers
51 views

Proofs and Number theory

I am needing help proving the following: For any integer $n$, $n^2$ + 5 is not divisible by $4$ I am aware that an integer $x$ is divisible by integer $y$ if there exists integer $k$ such that ...
7
votes
2answers
180 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
0
votes
1answer
49 views

Proving recurrence relations

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$. This is seen ...
0
votes
1answer
34 views

Using The Pigeon-Hole Principle

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Here is the solution: Let $a,~a+1,...,a+n-1$ be the integers in the sequence. ...
2
votes
1answer
65 views

Short proof of Hall's theorem

Studying the proof of Hall's theorem in my book I started to wonder if there is a shorter way to prove it. Following is an attempt that I think works but (being short) makes me wonder if I made a ...
3
votes
2answers
43 views

Solving two simultaneous recurrence relations

If we have the two recurrence relations $$a_n = 3a_{n-1} + 2b_{n-1}$$ $$b_n = a_{n-1} + 2b_{n-1}$$ with $a_0 = 1$ and $b_0 = 2$. My solution is that we first add two equations and assume that $f_n = ...
2
votes
2answers
53 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
33 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
1
vote
3answers
45 views

Can someone check the solution to this recurrence relation?

Here's the recurrence relation: $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$ Here's the solution:Write: $$ a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \quad a_0 = 1, a_1 = ...
0
votes
2answers
43 views

Finding this solution to a recurrence relation

So, I know that the recurrence relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$ has the solution of $a_n = -4(2^n) - n^2 / 4 - 5n / 2 + 1/8 + (39/8)(3^n)$. I just ...
0
votes
1answer
22 views

How to show all solutions for a particular recurrence solution

I've found that the recurrence relation $a_n = 4_{an−1} − 4a_{n−2} + (n + 1)2^n$ has the solution of $an = 2^n(p_0 + p_1n + n^2 + n^3/6)$. I'm just trying to understand the steps necessary to solve ...
2
votes
2answers
53 views

Finding the solution to this specific recurrence relation

What would be the solution to $a_n = 7a_{n−2} + 6a_{n−3}$ with $a_0 = 9$, $a_1 = 10$, and $a_2 = 32$ I can find it for a specific value of (n), but not for just a general solution. Thanks!
1
vote
0answers
35 views

Proving a specific recurrence relation theorem

I'm trying to come up with a proof for this theorem: Let $c_1$ and $c_2$ be real numbers with $c_2 != 0$. Suppose that $r^2 - c_1 r - c_2 = 0$ has only one root, $r_0$. A sequence $\{a_n\}$ is a ...
1
vote
2answers
44 views

Finding a solution to a recurrence relation

Find the solution to $$a_n = 5a_{n−2} − 4a_{n−4}$$ with $$a_0 = 3$$ $$a_1 = 2$$ $$a_2 = 6$$ $$a_3 = 8$$ My answer: Observe that the degree of recurrence is 4. Hence, the characteristic equation is: ...
1
vote
0answers
73 views

Is this theorem proof correct?

I'm trying to prove this theorem: Let $c_1$ and $c_2$ be real numbers with $c_2 \ne 0$. Suppose that $r^2 − c_1r − c_2 = 0$ has only one root $r_0$. A sequence $\{a_n\}$ is a solution of the ...
3
votes
3answers
48 views

Prove the following is a tautology

I was trying to prove this statement is a tautology without using truth tables. Something doesn't add it here as I keep getting stuck. Take a look please! For statements, P, Q and R prove that ...
4
votes
3answers
103 views

Proving or Disproving the Sum in a Set

I am doing review questions for an exam and I am completely stumped on this particular question: Let A = {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32}. Prove or disprove that if I select 10 distinct ...
1
vote
1answer
25 views

Finding the probability that X will be successful if its success is predicted

Consider an electronics company is planning to introduce a new camera phone. The company commissions a marketing report for each newproduct that predicts either the success or the failure of the ...
0
votes
1answer
55 views

Big-O Big theta Big omega papers

I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...
2
votes
3answers
106 views

Show that if $n$ and $k$ are integers with $1 ≤ k ≤ n$, then ${n\choose k} \le (n^k)/ 2^{k−1}$

I've looked everywhere but I've been unable to come up with a way to show that if $n$ and $k$ are both integers such that $1 ≤ k ≤ n$, then: $${n \choose k} \le \frac{n^k}{2^{k−1}}$$ Thank you!
1
vote
2answers
87 views

Can anyone help me understand this Strong Mathematical Induction proof?

I'm not sure if we're allowed to post pictures but I thought it would be easier to read and I didn't see anything in the rules about it. It's question 1. Section 5.4 This question: Here is the ...
1
vote
0answers
36 views

Find the number of permutations in these words

Finding the number of permutations in these three words, am I doing this correctly? a) CORRECT = $\frac{7!}{2!\cdot2!} = 1260$ b) COEFFICIENT = $\frac{11!}{2!\cdot2!\cdot2!\cdot2!} = 2494800$ c) ...
1
vote
1answer
18 views

How many permutations of this set can be made?

How many permutations of the set of seven letters (A,B,C,D,E,F,G) have the two vowels before the five consonants? I'm wondering here if we use the set of 7! - 2! since they can only occupy the first ...
1
vote
3answers
86 views

How many different permutations of this set don't have vowels on the ends?

If we have the set of seven letters: (A,B,C,D,E,F,G) then how many permutations of these seven letters do not have vowels on the ends (that is, both the first and last letters are consonants)? I was ...
2
votes
3answers
91 views

Prove$\overline{(A \cap B \cap C)} = \overline{A} \cup \overline{B} \cup \overline{C}$ By Subsets

This problem I am trying to solve is one I alluded to in this thread: Proving By Subsets I am having difficulty with proof by subsets, so I am aware that I am missing steps; I would certainly ...
8
votes
2answers
173 views

Prove that $\mathcal{P}(A)⊆ \mathcal{P}(B)$ if and only if $A⊆B$. [duplicate]

Here is my proof, I would appreciate it if someone could critique it for me: To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, ...
1
vote
3answers
123 views

Proving That The Product Of Two Different Odd Integers Is Odd

Okay, here is how I begin my proof: Let $q$ and $r$ be odd integers, then $q = 2k+1$ and $r = 2m+1$, where $k,m \in Z$. $q \times r = (2k+1)(2m+1) \implies q \times r = 4mk + 2k + 2m + 1 \implies q ...
0
votes
1answer
40 views

Showing the following language is not contex free

I need to show the following language is not context free via the Pumping Lemma. $$L = \{0^n\#0^{2n}\#0^{3n}\mid n \ge 0 \}$$ I was wondering if someone can help explain how to begin such a proof. ...
2
votes
1answer
68 views

Showing that the McCarthy Function is a well-defined function from the set of positive integers to the set of positive integers

For those of you who aren't familiar, the McCarthy Function states that M(n) = n − 10 if n > 100 and M(M(n + 11)) if n ≤ 100 (a recursive function). I'm trying to prove that this function is a ...
5
votes
2answers
66 views

Sipser Pumping Lemma Clarification

In a Theory of Computation book I am using, the explanation of Pumping Lemma is not bad, but some parts of it are not clear to me. Here is the Definition of Pumping Lemma: If A is a regular ...
1
vote
2answers
72 views

Prove by contradiction

Let $$ A = \cfrac {r_1 + r_2 + r_3 + \ldots + r_n}{n} $$ be the average of the real numbers $r_1, \ldots , r_n$. Prove there exists $i$ such that $r_i \ge A$. So this is obviously true because the ...
1
vote
3answers
680 views

Proving that a Turing Machine that only accepts even length strings is undecidable

I need to prove that a Turing Machine that only accepts even length strings in undecidable. The proof I was thinking is explaining the following: Given an input that contains even length strings, if ...
9
votes
4answers
262 views

Prove $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}} > 2\:(\sqrt{n+1} − 1)$

Basically, I'm trying to prove (by induction) that: $$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}} > 2\:(\sqrt{n+1} − 1)$$ I know to begin, we should use a base case. In this ...
0
votes
2answers
202 views

Discrete maths: proof by contradiction

Hi I'm new to discrete maths, and I have a prove by contradiction question. For example, say $15$ children together gathered $100$ marbles. How do I prove by contradiction that some pair of children ...
1
vote
5answers
107 views

How to prove that $n^2(2^n) / n! \to 0$ as $n \to \infty$

I'm trying to see how I can prove that : $$\frac{n^22^n}{n!}\xrightarrow [n\to\infty]{} 0$$ Not sure how to show this..anyone care to explain? Thanks!
1
vote
2answers
65 views

How to show that pairs of functions are of the same order?

If we have these pairs of functions, how can we show that they are of the same order? a) $3x + 7,\quad x$ b) $2x^2 + x − 7,\quad x^2$ c) $\lfloor x + 1/2\rfloor ,\quad x$ d) $\log(x^2 + 1),\quad ...
2
votes
1answer
87 views

Where is the flaw in the following proof?

Where is the flaw in the following proof, that if a language is Turing recognizable then we can enumerate it? Proof Let $TM1$ be a Turing machine for language $L$. We can create an enumerator $E$ ...
3
votes
3answers
127 views

Proving DeMorgan's Theorem

I'm trying to prove that (without using logical equivalencies): $\overline{A\cap B} = \bar A \cup \bar B$ by proving both sides: (1) $ x \in \overline{A\cap B} \to x \in \bar A\cup\bar B$ (2) $ x ...
0
votes
3answers
39 views

Picking A Certain Number Of Days Proof

The Problem is: Show that at least ten of any 64 days chosen must fall on the same day of the week. I know that in order to prove this, it's best to use a proof by contradiction. So, let's ...
1
vote
2answers
83 views

show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$.

I have to provide a structural proof for this: show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$. I have the following, ...
2
votes
3answers
251 views

Proving that the reciprocal of an irrational is irrational

The question I am working on is: Prove that if x is irrational, then 1/x is irrational. My proof differs from the one given in the answer key; but I still feel that mine is valid. Could someone ...
1
vote
2answers
267 views

Proof By Contradiction With Rational and Irrational Numbers

The question I am working on is: Use a proof by contradiction to prove that the sum of an irrational number and a rational number is irrational. After searching through Google, to see if this ...
1
vote
6answers
141 views

Proof Regarding Property of Odd Integers [duplicate]

The question I am working on is: "Use a direct proof to show that every odd integer is the difference of two squares." Proof: Let n be an odd integer: $n = 2k + 1$, where $k \in Z$ Let the ...
1
vote
2answers
148 views

Basic proof by Mathematical Induction (Towers of Hanoi)

I am new to proofs and I am trying to learn mathematical induction. I started working out a sample problem, but I am not sure if I am on the right track. I was wondering if someone would be kind ...
1
vote
1answer
35 views

Finding specific sets

I'm trying to calculate these particular sets given that: $$A=\{a,c,e,h,k\}$$ $$B=\{a,b,d,e,h,i,k,l\}$$ $$C=\{a,c,e,i,m\}$$ $$A \cap B$$ $$A\cap B \cap C$$ $$A \cup B \cup C$$ $$A-B$$ ...
3
votes
2answers
67 views

Proving that for any odd integer:$\left\lfloor \frac{n^2}{4} \right\rfloor = \frac{(n-1)(n+1)}{4}$

I'm trying to figure out how to prove that for any odd integer, the floor of: $$\left\lfloor \frac{n^2}{4} \right\rfloor = \frac{(n-1)(n+1)}{4}$$ Any help is appreciated to construct this proof! ...

1 2