The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

1
vote
2answers
82 views

Fourier Series of $\frac{\sin(x)}{x}$

Good afternoon! My teacher of signals and systems put in my test that calculate the Fourier coefficients for the function $f(x) = \frac{\sin x}{x}$. But ... How I can do? I know that the function is ...
4
votes
2answers
63 views

n bag of sand and one algorithms

We have $n$ bags of sand, with volume $$v_1,...,v_n, \forall i: \space 0 < v_i < 1$$ but not essentially sorted. we want to place all bag to boxes with volumes 1. We propose one algorithm: ...
0
votes
1answer
46 views

$X, Y$ be sets, $f:X→Y$ surjective map. For every $y ∈ Y$ , we put $Xy = f^{−1}(y)$. prove $Xy$ define partition of $X$?

Let $X$, $Y$ be sets, $f:X \to Y$ be a surjective map. For every $y \in Y$ , we put $Xy = f^{−1}(y)$. Prove that the sets $Xy$ define a partition of $X$? my try: since $f$ is surjective every $x$ ...
0
votes
1answer
23 views

Q: Basics of counting using rule of product

Lets say in a certain Univ, we are selecting committee members. Dep A has 10, Dep B has 15, and Dep C has 20 persons. How many ways can we select a committee if there should be a) 2 persons, and ...
0
votes
1answer
32 views

Chosing $2$ person from each groups using Product rule

Group A has $10$, Group B has $15$, and Group C has $20$ persons. What if only 2 persons can be chosen and they should be from different groups, what should I do? So far I can only think of simple ...
1
vote
1answer
19 views

I am trying to prove that a series has only non-integer entries after an element in the series.

I'm trying to prove that the series $a_n=\frac{6n}{4+n}$ has non-integer values for n>20. I attempted doing this by induction but couldn't get it to work.
1
vote
2answers
73 views

What is the flaw in this proof that uses induction?

Find the flaw in the following proof that $a^n = 1$ for all non-negative integers $n$, whenever $a$ is a non-zero real number. Proof: $P(n)\!:\ \forall k \leq n,\ a^n = 1$ where k is non-negative ...
0
votes
3answers
87 views

Robot on a grid. Find if it can reach a certain position. [duplicate]

We have a robot that can move : (+2, - 1) (-2, +1) (+1, +3) (-1, - 3) . I have to show whether it will reach a certain position (x, y) I've done that on a computer, recursively, but I can't ...
1
vote
1answer
65 views

Discrete mathematics generating function grabbing balloons restricted.

Say we have 3 different kind of balloons: blue, red and black. If we want to grab k balloons with the restriction that the number of red balloons is al least twice the number of blue balloons. How can ...
0
votes
2answers
141 views

Discrete - Determining how many times the print statement is being executed.

I'm quite bad at solving those kind of problems. Could you please guide me how to solve and how to approach the following? Determine how many times the print statement is executed. 1) ...
0
votes
0answers
50 views

Quantified Proposition Translation

I've been trying to translate the following sentence into quantified proposition. There is exactly one engineer who likes poetry. Let, $E(x)$ be '$x$ is an engineer' and $P(x)$ be '$x$ likes ...
2
votes
3answers
242 views

Quantified Proposition

I've been trying to translate the following sentences into quantified propositions by making sure I state all propositional functions that I use and any assumptions that I make. There is exactly one ...
1
vote
3answers
95 views

Proof by induction

The question is prove that for every integer greater than or equal to 2 $$\frac{1}{n+1} + \frac{1}{n+2} + \ldots + \frac{1}{2n} \geq \frac{7}{12}$$ So far I have Base case let $p(2)$ ...
0
votes
1answer
44 views

A mathematical expression for “grid search”?

I've got a question whether there is a mathematical expression for a grid search? I have two parameters a and b in [0;1]. Depending on the values of a and b, I get a value for my function (the value ...
1
vote
3answers
100 views

Use induction to prove that $n! \leq n^{n-1}$

Use induction to prove that $n! \leq n^{n-1}$ for all integers $n\geq 1$. I'm having a hard time with induction and my professor said this is a good future test like question if someone can post a ...
0
votes
1answer
35 views

Quantified Propositions

I've been trying to translate the following sentences into quantified propositions by making sure I state all propositional functions that I use and any assumptions that I make. Can you see if I'm on ...
0
votes
2answers
213 views

A robot moves on 2-Dimensional grid. It starts out at (0,0) and is allowed to move in any of these four ways:

A robot moves on 2-Dimensional grid. It starts out at (0,0) and is allowed to move in any of these four ways: 1. (+2,-1) 2. (-2,+1) 3. (+1,+3) 4. (-1,-3) Prove that this robot can never reach position ...
0
votes
2answers
103 views

Recursive definition of a set of strings.

Need assistant with this problem, Assume that $\Sigma=\{a,b\}$. Give a recursive definition of the set $E_a$ of all the strings $x\in\Sigma^*$ such that all the symbols occurring at the even positions ...
0
votes
1answer
39 views

Closed Form of a Generating Function

Given $\sum_{n \geq 0} a_n x^n$, where $a_n$ is the number of strings of length n all of whose entries equals 1, find a closed form. If I am correct so far, I have (0, 1, 2, 3, ...) as the counting ...
3
votes
4answers
269 views

How should you prove product rules by induction?

For example: $$\prod_{i=2}^n\left(1-\frac{1}{i^2}\right)=\frac{n+1}{2n}$$ For every $n$ greater than or equal to $2$ my approach for this was that I need to prove that: $$ ...
1
vote
1answer
42 views

interpreting partitions of integers(generating functions)

the question is: In $ f(x) = \left (\frac{1}{1-x} \right )\left (\frac{1}{1-x^2} \right )\left (\frac{1}{1-x^3} \right )$the coefficient of $x^6$ is 7. Interpret this result in terms of partitions ...
0
votes
2answers
118 views

how to determine the sequence generated by these generating functions?

I'm having hard time figuring out the sequence generated by each of these generating functions. $f(x) = {x^4\over (1-x)}$ $f(x) = {1\over (3-x)}$ $f(x) = {1\over (1-x)+3x^7-11}$ $f(x) = {1\over ...
0
votes
1answer
236 views

How to show a relation is/isn't reflexive, transitive, or symmetric

I was tasked with this: Define a relation on Z by setting x R y if xy is even. (a) Give a counterexample to show that R is not reflexive. How do I go about proving this? Do I express this ...
0
votes
1answer
26 views

Improving the proof by contraposition / why it works

This is the problem Prove that if n is an integer and 3n+2 is odd, then n is odd So for this I should take $3n+2$ to be true and assume $\lnot q$, therefore I ...
0
votes
1answer
56 views

Why reduce $64\bmod{11}$ down to $12\bmod{11}$?

This is the problem I am currently working on Find this value: $(7^3\bmod{23})^2\bmod{11}$ Here's my work: $$\begin{align*} &(7^3\bmod{23})^2\bmod{11}\\ &64\bmod{11}=9 \end{align*}$$ This ...
2
votes
1answer
52 views

$P \lor Q$ is Logically Equivalent to $P \land Q$?

For some reason I somehow came up with the logical equivalence of $(P \land Q) \equiv (P \lor Q)$ and I was hoping someone could point out the error in my reasoning, as I can't seem to find out where ...
0
votes
1answer
719 views

How many permutations of letters ABCDEFG contain the strings ABC and CDE

For this problem, I understand how to find something like how many strings contain the string BA and GF. I just look at the set of letters like this: {BA, GF, C, D, E} and since I have 5 distinct ...
0
votes
1answer
119 views

Number of derangements of of 8 distinct objects

I am currently doing this two part question and I am confused about the second part, can someone help explain how to do it? Part a) How many derangements of $$1,2,3,4,5,6,7,8 $$ start with 1,2,3, ...
1
vote
1answer
56 views

Prove $R$ follows from premises $(\lnot R\rightarrow\lnot Q),\;(P\lor Q,),\; (\lnot(P \lor T))$

I'm preparing for an exam and we weren't given an answer sheet. I'd like to know if my reasoning for the given conclusion is correct? Premises: $(\lnot R) \rightarrow (\lnot Q),\;\; (P \lor Q),\;\; ...
-1
votes
1answer
45 views

How to reduce a Boolean Algebra expression/function

I need to reduce this expression: $$F(A,B,C,D) = A'B'C'D + A'B'CD + A'BC'D + A'BCD' + AB'C'D + ABC'D' + ABCD'$$ I also have the following solution: \begin{align*} &= \bar A \bar B D + ...
0
votes
0answers
49 views

Lucas-Lehmer primality test and numbers form $k^{n}-1$

Is it possible to use Lucas-Lehmer test for testing the primality of numbers of the form $k^{n}-1$, where $k > 2$? For $k = 2$ (Mersenne number) $c_0 = 4$. What would be $c_0$ for $k > 2$?
1
vote
2answers
32 views

Express this with an existential quantifier and universal quantifier

Can someone verify I'm doing this correctly? English: No Humans live in the Ocean H(x): x is a human O(x): x lives in the ocean ...
0
votes
1answer
27 views

Give a proof of validity and indicate the law used

Below is what I'm trying to solve, I got to a certain point but am stuck. Can someone assist me with the correct steps to solve this? I could have potentially did a lot of it wrong too =/ Problem: ...
0
votes
1answer
194 views

How does (r-1) complement for subtraction work?

My instructor gave an algorithm for doing subtraction with (r-1)'s complement. For subtracting M - N, it goes like the following. 1) Find the (r-1)'s complement of N by using formula r^n - r^m - N. n ...
0
votes
1answer
126 views

Using rules of inference with quantified statements

Use rules of inference to show that (a) $ ∀x (R(x) → (S(x) ∨ Q(x))$ $∃x (¬S(x))$ $ ∃x (R(x) → Q(x) )$ I'm kinda lost at what to do... I can start but don't know what to do afterwards 1) $R(a) ...
0
votes
0answers
74 views

Changing money combinatorics?

The following coins were in circulation in the United States in 1875: Indian-head penny, a bronze two-cent piece, a silver three-cent piece, a nickel three-cent piece, the shield nickel (worth ...
0
votes
0answers
85 views

Let p1, p2, ..pk be prime integers. if n = p1p2…pk + 1 then for every i, i =1, 2…,k, pi does not divide n.

I'm told to this by contradiction which seems quite simple at first but I think I might be neglecting something. I would simply let n be product of p1p2...pk + 1. and let m equal p1p2..pk. I then say ...
1
vote
1answer
68 views

Discrete Math Boys and Girls

Problem 4: Boys and Girls Consider a set of m boys and n girls. A group is called homogeneous if it consists of all boys or all girls. In the following questions, practice the multiplication and the ...
2
votes
0answers
25 views

How many blocks in this set differ from the original in one exactly one way?

This is an example problem that I worked out but I'm not sure if it's correct since we weren't given an answer key. The full problem reads: Dustin has a set of blocks. Each of these blocks is made of ...
0
votes
1answer
40 views

Is this example of an ordered set correct?

Example of an ordered set: Let us define a set $C$. Let $C$ is the set of circles of all radii. The circles are all lying on a plane. (The point circle is excluded.) If we take any two circles ...
0
votes
1answer
28 views

Number of Different Chains with Length N

There 2 types of balls Red, and Blue. Any Red ball can be marked by the letters A, B or C. Any Blue ball can be marked by the letters D, E, F. Let's mark by $ {a}_{n} $ the number of different chains ...
1
vote
1answer
65 views

Find the number of bit strings which start with four zeroes and end with three ones

Count the number of bit strings that start with four $0$'s or end with three $1$'s if the length of the bit string is: $7$ $4$
0
votes
1answer
402 views

How to evaluate growth of input size from n to 2n in this case?

This is the question I am currently working on What is the effect in time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the ...
0
votes
2answers
98 views

A sequence of 5 cards is drawn from a standard 52-card deck,with replacement. How many sequences will have at least one king or one queen, or both?

Total number of sequences without a king or a queen is $44^5$, so the total number of sequences with at least one occurrence of a king or a queen is $52^5 - 44^5$, is that correct?
1
vote
1answer
76 views

Usage of the term “perfect matching” for bipartite graphs

A textbook written by my discrete mathematics teacher defines a "perfect matching" in a bipartite graph as a matching that covers at least one side of the graph (i.e. for $G = (V1, V2, E)$ with $V1$ ...
0
votes
1answer
33 views

NFA from regular grammars

I am trying to make an NFA from this regular grammar $$\{a^n \mid n > 0\}\cup \{b^m a^k \mid m\ge 0,k \ge 0\}\;.$$ This is what I have now. The last part, $a\ge 0$, is the one I am not sure ...
1
vote
0answers
28 views

Cardinality of sets 2015

Let $A,B \subset\left\{1,2,3,\ldots\right\}$ be disjoint sets and let the number of elements ,$n(A)=m ,n(B)=k.$ Then what is $n(A+B) ?$ where we define $$A+B=\left\{i+j:i\in A,j\in B\right\}.$$ Any ...
1
vote
1answer
172 views

Help with a propositional logic question

The question goes like this: For each of the arguments below, formalize them in a propositional logic. If the argument is valid identify which inference rule was used, and formulate the tautology ...
3
votes
4answers
612 views

Strong induction with Fibonacci numbers

I have two equations that I have been trying to prove. The first of which is:F(n + 3) = 2F(n + 1) + F(n) for n ≥ 1.For this equation the answer is in the back of my book and the proof is as follows:1) ...
1
vote
1answer
32 views

Find all nonnegative integers n, that satisfy the equation P(n, 2) = P(4n − 6, 1)

I have the equation P(n, 2) = P(4n - 6, 1) and I need to find all non negative integers which satisfy it. I understand that this equation can also be written as n!/(n-2)! = (4n-6)!/(4n-5)! and ...