1
vote
2answers
48 views

If $a_i>o$ then $(a_1a_2\cdots a_{2^n})^{1/2^n}\leq \frac{a_1+a_2+\cdots+a_{2^n}}{2^n}$

I need help to prove this inequality, I have no idea how to proceed with the inductive step: $$a_1,a_2,\ldots,a_{2^n}>0 \Longrightarrow(a_1a_2\cdots a_{2^n})^{1/2^n}\leq ...
1
vote
1answer
31 views

Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
0
votes
1answer
62 views

The Pigeonhole principle and sum of integers in subset of Z

S⊂{1,2,3,...} and the cardinality of S is 7. m is the maximum element in S.Find the possible values of m so that there exists distinct subsets B,C with s(B)=s(C) [s(B) means the sum of the objects in ...
1
vote
1answer
33 views

Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
2
votes
2answers
50 views

Binary relation, reflexive, symmetric and transitive

I have a question regarding an image. I'm currently studying binary relations and the following image confused me: What got me confused is that the page from which I got the link ...
4
votes
1answer
39 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
0
votes
2answers
30 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
2
votes
1answer
42 views

Proof Verification for Discrete Math Class

Prove that $n^2$ is even iff $n$ is even. I proved it like this: Case I: $n$ is even 1) $n = 2a$ $(a\in Z)$ 2) $n^2 = 4a^2 = 2(2a^2)$ 3) $2a^2 = K$ $(K \in Z)$ 4) $n^2 = 2K$ Case II: $n$ is ...
0
votes
1answer
21 views

Check these recursive definitions for me?

Looking for Give a recursive definition of A) the set of odd positive integers B) the set of positive integer powers of 3 C) the set of polynomials with integer coefficients I have a. Basis: ...
0
votes
0answers
43 views

Verification of a Combinatorial Identity

I was given a question and would like to see if I made any errors in my answer. The Question: My Answer: I noticed the following identity is very useful here: $\dbinom{n+1}{r}$ = $\dbinom{n}{r}$ ...
0
votes
3answers
98 views

Find the problem with this proof.

The following attempts to prove that if $n^2$ is even, then $n$ is even. Suppose $n^2$ is even. Then $n^2$ = 2$k$ for some integer $k$. Let $n$ = 2$m$ for some integer $m$. This shows that $n$ is ...
1
vote
2answers
63 views

Proof Verification for Homework

If $n$ is odd, then $n^2$ is odd. $1$) $n = 2k + 1$ (Definition of an odd number) $2$) $n^2 = (2k+1)^2 = (2k+1)(2k+1) = 4k^2 + 4k + 1$ (Distributive Property) $3$) $4k^2 + 4k + 1 = 2(2k^2 + 2k) + ...
2
votes
1answer
47 views

Graphs without nontrivial automorphism

I'm trying to solve two problems about graph automorphisms. I want to construct a bipartite graph without a nontrivial automorphism. I want to find the smallest possible number of nodes for a graph ...
2
votes
2answers
90 views

Proof by induction that $(1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2$

I'm sitting with the proof in front of me, but I do not understand it. $$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$ The first step of proof by induction is ...
1
vote
2answers
21 views

Inverse of a composite function

In a homework assignment, I am asked to find $(P_3 \circ P_1)^{-1}$ knowing: Let $P_1 = (3\ 4\ 1\ 2\ 5), P_2 = (3\ 5\ 1\ 2\ 4)$ and $P_3 = (5\ 1\ 4\ 2\ 3)$ be three permutations. I am second-guesing ...
1
vote
1answer
43 views

Cartesian Product of $\emptyset \times \emptyset$

A bit of homework that I'm not sure on. The question reads: Let $A=\{a\}$ and $B=\{1,2\}$. Find the following: $$\mathcal{P}(A) \times \mathcal{P}(B)$$ The worked out solution is as follows. $\{ ...
0
votes
1answer
132 views

Prove that $\lambda(v-1) = r(k-1)$

This is to do with balanced incomplete block design. Some homework exercise wants me to prove the relation $$\lambda(v-1) = r(k-1)$$ $v$ is the number of elements in your ground set. $r$ is the ...
2
votes
2answers
101 views

Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I'm trying to find the largest number $n ...
1
vote
1answer
50 views

Boolean Functions and using rules ..

Is the function $p \wedge (~\neg(\neg p \vee q) \vee (p \wedge q))$ equal to the function $p \wedge q$? Do I need to provide a truth table for this, or do I have to use the rules (for Manipulating ...
0
votes
2answers
37 views

Divide and Conquer Recurrence Relation help?

So the divide and concur recurrence has to be of the form H($n$) = $a$H($n$/$b$) + $cn^d$. I already figured out that $a$ = 4 and $b$ = 2. I am really stuck on how to find $cn^d$ however. I ...
1
vote
0answers
34 views

How to find the lengths of the shortest paths in a directed graph in $O(m)$ steps?

Let $G = (V,A)$ be a directed graph for which it is true that if $(v_i , v_j) \in A$, it is implied that $i < j$. Question: How does one construct an $\mathcal{O}(m)$ algorithm to find the ...
2
votes
2answers
56 views

feedback on my solution regarding eqivalence relations. [duplicate]

For all $x, y \in \mathbb{R}$ define that $x \equiv y$ if $x^2 = y^2$. Then $\equiv$ is an equivalence relation on $\mathbb{R}$, there are infinitely many equivalence classes, one of them consists of ...
0
votes
1answer
87 views

Feedback on my answer for $X^n + Y^n = Z^n $ [duplicate]

The equation $X^n + Y^n = Z^n $ , where $n \ge 3$ is a natural number, has no solutions at all where X; Y;Z are integers. solution: the above is a false statement counter example: let: n=3 ,x=0 y=0 ...
1
vote
1answer
31 views

Expressing the generating function defined by $b_n = \sum_{k=0}^{n} 3^k\cdot a_k$

The title is probably somewhat unclear, sorry if it is.. Let $F$ be the generating function of the sequence $(a_n)_{n=0}^{\infty}$ Use $F$ to express the generating function for ...
2
votes
3answers
65 views

Induction: Prove that it is possible to seat people in a circle so that everyone sits beside a friend

Use induction to prove the following: If each person in a group of $n$ people is a friend of at least half the people in the group, then prove that it is possible to seat them in a circle so that ...
0
votes
1answer
29 views

Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log ...
0
votes
1answer
42 views

A problem of Set Theory

The question is : In a market survey,a manufacturer obtained the following data : Did you use our brand? Percentage answering yes 1. April 59 2. May ...
0
votes
2answers
51 views

integer solution to an equation - do solutions exist?

prove or find a counterexample: The equation $x^n + y^n = z^n$, where $n$ is a natural number, has no solutions at all where $x, y,z$ are integer. counterexample: if $n=3$ and $x=1$ and $y=2$ and ...
1
vote
1answer
38 views

Question about Big O Notation

I don't seem to understand big-O notation very well. If someone would explain it to me as well as explain how this problem would work Let f(n) = (3$^n$$^+$$^1$ - 3)/2. For each of the following ...
1
vote
0answers
47 views

Determine the number of integer solutions of $x_1 + x_2 + x_3 + x_4 + x_5 = 32$ where $x_i \gt 3$ for $1 \le i \le 5$

I've got some homework that asks: Determine the number of integer solutions of $x_1 + x_2 + x_3 + x_4 + x_5 = 32$ where $x_i > 3$ for $1 \le i \le 5$. My solution is as follows: $C(32 + 5 - 1, ...
1
vote
2answers
49 views

Proving a triangle with different edge colors exists in a graph.

This is again some homework translated (hopefully not too badly) from my book The graph $K_{n}$ is colored using $n$ different colors, in a way that each color is used at least once. Prove that there ...
1
vote
2answers
45 views

How to prove or disprove $P(\overline A) = P(U) - P(A)$

Edit: P(U) and P(A) refer to Power Sets. I don't know how to prove, or disprove, $P(\overline A) = P(U) - P(A)$. My initial thoughts is that the statement is true: If I have a set A in universe U, ...
0
votes
0answers
13 views

Indicate the interpretation in which the following formula is valid: (Ax)(Ey) p(f(x),y) -> (Ey)(Ax) q(x,g(y))

Let us consider a structure, where U is the universe and f, g are one-argument operations and p, q are two-argument predicates. Indicate the interpretation in which the following formula is valid: ...
0
votes
0answers
5 views

The following propositional functions are defined

The following propositional functions are defined in the set of all real numbers R. Let Sat(f) be the set of all values of y which satisfy f(y). Indicate functions or function for which Sat(f) = R? ...
0
votes
2answers
21 views

For which a and m does there exist integer b for ab mod m=1

a. a = 5, m = 8 b. a = 29875, m = 75 c. a = 3, m = 79 d. a = 13, m = 91 I've figured out that A. is correct just by plugging in numbers for b, but I have no idea how to figure it out with the other ...
0
votes
1answer
26 views

Equivalence Relation ~

let S = {1,2,3,4} Explain why each of the below are not equivalence relation. { (1,1), (1,2), (2,1), (2,2), (3,3) } { (1,1), (1,2), (2,3), (1,3), (2,2), (3,3), (4,4) } { (1,1), (2,2), (3,3), ...
0
votes
1answer
40 views

Discrete Math True or False

1.$\mathcal P(A\setminus B) = \mathcal P(A) \setminus P(B)$ These are power sets. False. 2.If $G$ is bipartite, then the complement of $G$ is disconnected. False. 3.Suppose $\mathcal F$ and ...
0
votes
1answer
36 views

Prove a relation is a equivalence

Let $\sim$ be defined so that $a\sim b$ when $a+b$ is even. Is this an equivalence relation? Equivalence relations confuse me a lot, so any help is appreciated!
0
votes
1answer
18 views

Graph Isomorphism with Same Degree Sequece

How do I prove that two tree graphs with the same degree sequence are isomorphic (or non isomorphic)? Thanks for the help!
1
vote
2answers
52 views

Prove a 4-cycle exists in a graph with 100 vertices, each with degree of atleast 50

I hope I wrote the question well since it is my attempt at translating from the book. If it isnt clear enough, The question states that in every graph as described in the title a simple cycle of ...
0
votes
1answer
48 views

Help With sets!

Can someone help me solve this question please?? Pretend you are writing traffic accident software and want to categorize accidents by the day of the week on which they occur. Pretend there are n ...
1
vote
1answer
44 views

Discrete Math On Recurrence

Suppose that a geometric sequence starts with and satisfies the recurrence $a_n = ra_{n -1}$ for every positive integer $n$. a) Show that $a_n = a_0rⁿ$. b) Find the 100th number in the sequence ...
-1
votes
1answer
52 views

Prove by indution

Can someone help me with this homework question. Prove the following by induction $$\sum_{k = 1}^n k {n \choose k} = n \cdot 2^{n - 1}.$$ Thanks
1
vote
2answers
27 views

Ball Probability help

A bowl contains 5 red balls, 3 white balls and 2 blue balls. Two balls are seleceted at random from the bowl (without replacement). A) What is the probability that both are red? which is 2/9 B) What ...
0
votes
2answers
95 views

Prove $x$ and $y$ in $y = x^2 + 2$ are prime only for $x = 3$ and $y = 11$?

Let $x$ be a positive integer and $y = x^2 + 2$. Can $x$ and $y$ be both prime? The answer is yes, since for $x = 3$ we get $y = 11$, and both numbers are prime. Prove that this is the only value of x ...
0
votes
1answer
119 views

find the recurrence relation (homework)

I'm new to recurrence relations and I'm having trouble figuring out this problem: Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two ...
0
votes
1answer
38 views

Defining a bijective function from $2\mathbb{N}$ to $3\mathbb{Z}-1$?

$2\mathbb{N}=\{2n:n\in\mathbb{N}\}$ and $3\mathbb{Z}-1=\{3n-1:n\in\mathbb{Z}\}$ Work: So far, my plan is to first define a bijective function from $2\mathbb{N}$ to $\mathbb{N}$ and then define ...
0
votes
3answers
52 views

Proving that function $f:[0,\infty)\rightarrow [0,\infty)$ defined by $f(x)=\frac{x^2}{1-x}$ is bijective.

I am having a bit of trouble with the algebra for proving that the function is injective. Basically I set $f(a)=f(b)$ for $a,b\in[0,\infty)$ and $a,b\neq 1$. ...
0
votes
1answer
28 views

Statistics with discrete math

I am working on a homework problem and I think that I am doing this correctly but i am not sure. This is the question: An upper-level math class has 13 students: 4 of them are females. Two of the ...
2
votes
0answers
13 views

Finding the number of relations on set S

I know the number of reflexive relations on a finite set is: $2^{n^{2}-n}$ The number of symmetric relations is: $2^{n+1 \choose 2} $ The number of antisymmetric relations: $2^{n}3^{n \choose 2}$ ...