Tagged Questions

0
votes
1answer
14 views

Clues to prove average in T is minor or equal than average in a smaller inner interval.

Suppose I want to prove (or disprove) this assertion Let $f$ be a discrete function, $T,h,k$ are constants So these terms are averages over $T$ and over $h$ $\sum\limits_{i=0}^{T}\frac {f(i)}{T}$ ...
2
votes
2answers
56 views

How do I prove the arithmetic-geometric mean inequality?

I am following along with this bare-bones proof of the arithmetic-geometric mean inequality with two real numbers. I'm having difficulty understanding the logic behind this step: $$ ...
0
votes
1answer
36 views

Finding a reccurence relation for the following problem

A circular disk is cut into n distint sectors, each shaped liek a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
-2
votes
1answer
50 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
110 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$
-1
votes
1answer
56 views

Proof of divisibility by 2 and 3 if and only if divisible by 6

I can't find a way of proving that: For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6. I’m not sure where to go from here. Any help would be great!
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 ...
3
votes
2answers
41 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 = ...
1
vote
3answers
44 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
42 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 ...
1
vote
2answers
48 views

Find the recurrence solution of this relation

How would we find the solution of the recurrence relation: $a_n = 2a_{n−1} + 3 · 2^n$ ? After trying it, I've found it to be $a_n = 2^{n-1} (c_1 + 6n)$ Not sure if this is right.. Thanks!
2
votes
2answers
51 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
34 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: ...
3
votes
1answer
41 views

Finding a Linear Recurrence Relation

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years. ...
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 ...
4
votes
3answers
101 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
24 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 ...
3
votes
1answer
31 views

Binomial coefficient help?

I'm studying for my exams and would appreciate any help with binomial coefficients. I think I got the idea but having trouble with a specific one: Q) If a there are 11 dogs and 9 cats: a) How many 7 ...
1
vote
3answers
76 views

For all sets $A$ and $B$, if $A^c ⊆ B$ then $A ∪ B = U$

For all sets $A$ and $B$, if $\;A^c ⊆ B$ then $A ∪ B = U$ I am having difficulty starting to disprove an alleged set property through the use of a counterexample or if it is true then try to ...
1
vote
3answers
39 views

For all sets $A$ and B, if $B ⊆ A^c$ then $A ∩ B = ∅$

I made a Venn Diagram so I know that this is true. Now I just need some help on getting the proof right. For all sets $A$ and B, if $B ⊆ A^c$ then $A ∩ B = ∅$ I have started the proof: Suppose $A$ ...
-3
votes
2answers
67 views

If $P(n)$ is true for $n = 1$, if $P(n)\implies P(2n)$, and if $P(n) \implies P(n - 1)$, then $P(n)$ is true for all $n$. [closed]

Assume that the statement P(n) is true for n = 1 and that P(n) → P(2n) for all n ∈ ℕ. Furthermore assume that if n > 0 then P(n) → P(n - 1). Prove (∀n ∈ N)P(n). The following two exercises deal with ...
0
votes
2answers
67 views

Mathematical Proof Question?

How would prove that this is true for all $k \geq 6$: $$\left(\frac{1+\sqrt{5}}{2}\right)^{k+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k+1} \geq (1.5)^{k} \times \sqrt{5} $$
2
votes
3answers
98 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
0answers
34 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
83 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 ...
1
vote
1answer
29 views

Pointers about the concept of 'division extensionality'?

When working a bit on another question (If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$), I discovered the following, which seems to be valid: $$ a = b \;\;\equiv\;\; \langle \forall d :: d ...
2
votes
3answers
90 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 ...
-2
votes
1answer
90 views

Proving By Subsets [closed]

I am currently trying to learn about conducting proofs by using subsets. In my textbook, there is an example on this very matter; however, the seem to do something that is in contradiction with what ...
0
votes
1answer
98 views

Induction proof on covering a checkerboard with dominoes - don't think my proof is right.

So I'm trying to solve this problem and I think I'm on the write track, but my proof relies on a domino being divisible by 2, which I don't think is correct. The problem: Prove that a $2^n \times ...
8
votes
2answers
169 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
121 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. ...
5
votes
2answers
65 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
3answers
656 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 ...
0
votes
3answers
62 views

(Dis)prove that: $\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$

So I'm trying disprove this statement. Well, I'm pretty sure it's wrong because it doesn't work when $a = 0$ . I'm just not sure if all I need to do is give that counterexample, or if there is a way ...
3
votes
1answer
93 views

Proving a function is big O

How would I go about proving a function is big O? Do I use the regular proofs (direct, contrapositive, contradiction)? Example: Prove that $x^n$ is $O(n!)$ for every real number $x$. My proof by ...
1
vote
1answer
82 views

Proving Complement Laws

The problem I am working on is: Proof the following: $A∪ \bar{A}=U$ As with all proofs, I commenced this proof by using the definition of a union: $A∪ \bar{A} = \{x|x \in A \vee x \in ...
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
2answers
66 views

proving if a number is prime or not using combinations

I am really confused on this problem. I am given that $p$ = prime number, $1 \leq k \leq p-1$, and am asked to show $\binom{p}{k}$ multiple of $p.$ How do I prove that $\binom{p}{k}$ is a multple ...
2
votes
3answers
107 views

Prove that $\sum_{k=0}^n \binom{n}{k} k^2 = n(n+1) 2^{n-2}$ [duplicate]

$$\sum_{k=0}^n \binom{n}{k} k^2 = n(n+1) 2^{n-2}$$
4
votes
2answers
281 views

Showing there is no integer solution to equation $2^x = 4y+3$

I am stuck on this problem and I'm not sure how to approach it, can anyone help me out with figuring how to solve the solution. The question is: Prove that it is impossible to find integers $x, ...
1
vote
2answers
251 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
137 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 ...
4
votes
4answers
124 views

Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$

Prove by Mathematical Induction . . . $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$ I tried solving it, but I got stuck near the end . . . a. Basis Step: $(1)(1!) = (1+1)!-1$ $1 = ...
0
votes
3answers
35 views

Identifying Proof Method and Implementing It

The question I am working on is: Prove that if $m+n$ and $n+p$ are even integers, where $m$, $n$,and $p$ are integers, then $m+p$ is even. What kind of proof did you use? I was thinking--and ...
3
votes
3answers
50 views

Proving that for any odd integer: $\large \lceil \frac{N^2}{4} \rceil = \frac{N^2 + 3}{4}$

I'm trying to construct a proof that for any odd integer: the ceiling of $\large \lceil \frac{N^2}{4} \rceil = \frac{N^2 + 3}{4}$. Anyone have a second to show me how this is done? Thanks!

1 2