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

0
votes
1answer
49 views

Prove a complement of a union and intersection of two sets?

So our teacher asked us to prove that $(A\cup B) \setminus (A \cap B)$ = $(A \cap \overline{B}) \cup (\overline{A} \cap B)$ Obviously the statement makes sense when I look at it, but actually ...
4
votes
4answers
362 views

Mathematical Induction Question, Proof Help [duplicate]

Prove using Mathematical Induction that for all natural numbers ($n>0$): $$ \frac 1 {\sqrt{1}} + \frac 1 {\sqrt{2}} + \cdots + \frac 1 {\sqrt{n}} \ge \sqrt{n}. $$ ...
0
votes
1answer
455 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
0
votes
1answer
23 views

Discrete Relation Properties

I can not get a grasp on Relations. Any help would be great. Prove that if R􏰄 is a symmetric relation, so is R^2􏰄􏰇.
1
vote
1answer
139 views

The composition of the $<$ relation with itself

I am struggle with answering this question. I do not understand how to approach this question. 1.Let <􏰈 denote the less than relation on the set of integers. Describe the squared relation <^2 ...
1
vote
2answers
67 views

Direct proof (Logic)

I need help, I've to give by resolution a direct proof of I've made a conjunction and got: How do I give a direct proof by resolution?
0
votes
1answer
65 views

How to prove that multinomial theorem in combination

Show that the coefficient of $x^n$ in $$\left ( 1+x+x^{2} \right )^n$$ is $$1 + \frac{n(n-1)}{(1!)^2}+\frac{n\cdot (n-1)\cdot (n-2)\cdot (n-3))}{(2!)^2}+\cdot \cdot \cdot \cdot \cdot \cdot $$ I know ...
1
vote
1answer
40 views

Prove or disprove the inequality

Let $d,\ a,\ x,\ b,\ y $ be integers. $d$ divides $a$ and $b$. The question is: Assume $ax + by \gt 0$. Prove or disprove : $d \le ax + by $ I know that $d | ax+by$, but I can't figure out the ...
2
votes
3answers
60 views

How to derive the closed form of this recurrence?

For the recurrence, $T(n) = 3T(n-1)-2$, where $T(0)= 5$, I found the closed form to be $4\cdot 3^n +1$(with help of Wolfram Alpha). Now I am trying to figure it out for myself. So far, I have worked ...
2
votes
3answers
84 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
1
vote
1answer
474 views

How many nonnegative integer solutions are there to the pair of equations $x_1+x_2+…+x_6=20$ and $x_1+x_2+x_3=7$?

How many nonnegative integer solutions are there to the pair of equations \begin{align}x_1+x_2+\dots +x_6&=20 \\ x_1+x_2+x_3&=7\end{align} How do you find non-negative integer solutions?
0
votes
1answer
62 views

How can I justify it formally?

Given the following algorithm: Function Fun(int n){ int j,k,t=1; for (j=0; j<=4n^2; j+=4){ for (k=j; k<=4*sqrt(n); k+=4){ t+=8; } } } I ...
1
vote
1answer
70 views

Is there an error-correcting code where almost every word could be used as a codeword?

An error-correcting code for strings of length $n$ from a $K$ letter alphabet is a partition $\Pi$ of $K^n$ together with a choice function $\pi$ on $\Pi$. Let $A_i$ for $i<M$ enumerate $\Pi$, and ...
1
vote
1answer
36 views

Why does the following formula cycle the bits by shifting the binary representation from left to right?

Intuitively, I was trying to come up with a formula that would cycle through the binary representation of numbers from left to right. Let our range of numbers goes from $0, .., N-1$ and let $m$ ...
1
vote
1answer
56 views

How many bit strings of length 7 exist if the string remains unchanged if it is reversed?

How many bit strings of length 7 exist if the string remains unchanged if it is reversed ? 1 1 1 1 1 1 1 and 1 0 0 1 0 0 1 are an example that is unchanged if reversed. 0 0 0 0 0 0 0 and 0 1 1 0 1 1 ...
6
votes
1answer
268 views

Recursion relation of fourth order Runge-Kutta method applied on system

I'm trying to apply the Gauss-Legendre method of fourth order (as Runge-Kutta method) on the following system of equations $$\left\{ \begin{matrix} \dot{a} =& -b \\ ...
0
votes
1answer
62 views

Large Family of Subsets with small overlap

Find upper and lower bounds on the cardinality of the largest family of subsets of an $n $ element set, $\mathcal{S}\subset \mathcal{P}(\{1,\dots ,n\})$ , if no pair of elements contain a third ...
1
vote
1answer
28 views

Logic behind rule of product solution for a question

Im working through a book of Discrete and combinatorial mathematics and there is one question that I answered correct, however the solution in the book is very different (and it seems far more ...
1
vote
2answers
26 views

Given that $p$ is prime, $\gcd(a, p^2) = p$ and $\gcd(b, p^3)=p^2$ find $\gcd(a+b, p^4)$

Given that p is prime, $\gcd(a, p^2)=p$ and $\gcd(b, p^3)=p^2$ find $\gcd(a+b, p^4)$. I'm really not sure how to approach the problem. My intuition from looking at it makes me think that the answer ...
0
votes
2answers
22 views

Is proof by modular arithmetic appropriate in this syntax?

I have a question which asks: Prove there are no integer solutions for the equation: $$4x = y^2 +1 $$ To prove, lets take $\pmod4$ of both sides, such that: $$ 4x\pmod4 = (y^2 +1)\pmod4$$ $$ ...
1
vote
1answer
249 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
0
votes
1answer
75 views

How many distinct functions can be defined from set A to P(B)?

A is a set with n elements. B is a set with m elements. How many functions are there from A to P(B)? I am not sure if my thinking is correct. If B is a set with m elements so P(B) = 2^m . Each ...
1
vote
2answers
82 views

Evaluate $\sum_{k=1}^{99}C(100,k)4^{k+2}$

Evaluate the following sum and show your work. Leave expressions of the form ݉$m^n$ in your answer without attempting to evaluate them. Solutions that rely solely on calculator computation of the ...
1
vote
2answers
58 views

Members of the sequence greater than 1 less than N

Suppose N is a positive integer. How many decreasing integer sequences are there such that members of the sequence are greater than 1 but less than N… I have tried to come up with an expression for ...
2
votes
1answer
48 views

Intuition for Euler's Partition Theorem

Euler's Partition Theorem states the following: Every number has as many integer partitions into odd parts as into distinct parts. I played around with small examples (I wrote out the partitions ...
0
votes
0answers
97 views

Determining the smallest burst error a system cannot correct.

Working on a question. I have an answer but fear I may have lost my grasp on the knowledge of this topic part way through as it seems I got to the answer too easily. So the question is: An error ...
0
votes
1answer
59 views

How to find the inverse of f?

$ f : A \rightarrow B $ where $ A = B = \left \{4,5,6,7 \right \} $ $ f = \left \{ (4,6),(5,5),(6,7),(7,5) \right \} $ Find $ f^{-1} $ I know how to find the inverse of $ f $ if it were ...
1
vote
0answers
53 views

Are all of these proofs solved the same way?

$\forall x \in \Bbb R , \exists y \in \Bbb Z$ so that $\lfloor xy \rfloor = \lfloor x \rfloor \lfloor y \rfloor $. Assume that $x \in \Bbb R, y \in \Bbb Z.$ Let $\lfloor x \rfloor = n$ for ...
0
votes
4answers
62 views

Is there a counterexample to “For all integers $a,b, d$, if $d\mid(3a+2b)$ and $d\mid(2a+b)$, then $d\mid a$ and $d\mid b$.”

I've tried to solve this problem, but I keep getting stuck at the end. Assume $a, b$ , and d are integers and $d$ $\neq$ 0. $3a+2b = dm,\,\,\,$ for some integer $m$. $2a+b = dn,\,\,\,$ for ...
2
votes
2answers
101 views

Discrete Math — Sets

I am struggling with thinking about this. Any help would be great!! A medical research survey categorizes adults as follows: by gender (male or female) by age group (age groups are 18-25, 26-35, ...
11
votes
2answers
910 views

Discrete math. Finding a perfect square.

The problem is: Find all natural numbers $n$ for which $2^n + 1$ is a perfect square? I am having a bit of trouble finding a generic way of finding these numbers. Of course the first obvious solution ...
1
vote
2answers
49 views

Logarithmic part of the Risch Alorithm

I'm reading some paper about the Risch algorithm and wanted to try a little example: I want to find an elementary solution for: $$\int\frac{1}{e^x + 1}$$ The following lemma tells me how to do ...
1
vote
2answers
122 views

Discrete Math problem combinations and restrictions

I am trying to get my head around an idea but I can't seem to get it to work. Imagine you have the word "MAMMAL" Lets see I wanted to figure out how many ways I could rearrange the letters. Well ...
1
vote
0answers
54 views

Discrete Fourier Transform by hand

I have an assignment where I'm given the DFT of a sequence $x[n]$ as $X[k]=\{4,3,2,1,0,1,2,3\}$ and also $$y[n] = \left\{ \begin{array}[cc] xx[n/2] & \text{if n is even} \\ 0 & ...
3
votes
2answers
110 views

predicate quantifier

a)There is a tree in the back yard. b)If the tree in the back yard is an elm or an oak, then the treasure is in the kitchen and not in the garage. c)If this house is made of bricks or the tree in ...
2
votes
2answers
154 views

Big-O Function for f(x)

I'm currently taking a Discrete Mathematics course which just started the chapter on The Growth of Functions. A (very) brief overview was given in lecture that covered the Big-O definition. Let ...
0
votes
3answers
52 views

Prove by induction for every integer$\; n\ge 5$, $2^n\gt n^2$.

Prove by induction for every integer$ \;n\ge 5$, $2^n\gt n^2$. My try: $$p(n):\;2^n>n^2$$ verify $P(5)$ $$ p(5):\;2^5>5^2 = 32 > 25 $$ Of course the trick is in the induction step and ...
1
vote
1answer
19 views

Sequence problem by Strong induction

Problem is as follows: Let $X_0 = 3$ and let $X_{n+1} = X_n + \cdots + x_1 + x_0 + 3$ for $n ≥ 0$. Show that $3|X_n$ for all $n ≥ 0$. I have the base case where $n=0$. Therefore $X_0=3$ and $3|0$. ...
1
vote
1answer
48 views

Help coming up with a optimal function

I am working on solving this problem: https://open.kattis.com/problems/tractor Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a ...
0
votes
1answer
143 views

Could someone help me out with permutations/combinations?

I need some help understanding how to approach problems with permutations/combinations. Could someone first explain when I should be using combinations and when I should be using permutations? Then ...
0
votes
1answer
77 views

Permutation question in discrete mathematics. At least 1 out 3 members (P) from a total of 10 members

Im doing a question out of Discrete and Combinatorial mathematics by Grimaldi (4th Edition). Im stuck on one of the questions and am trying to find an alternative way of doing it, that is not in the ...
0
votes
1answer
44 views

If $a \in \mathbb{N}$, prove that gcd$(a, a+2)$ is $1$ if $a$ is odd and $2$ if $a$ is even.

Once again the problem is: If 'a' is an element of N, prove that gcd(a, a+2) is 1 if 'a' is an odd number, and 2 is 'a' is an even number. I really have no idea on how to prove this, and I'm brand ...
3
votes
1answer
45 views

A room and a spider

A room has the shape of a rectangular cuboid. The edges are 3, 4 and 5 metres. There is a spider in one of the corners. The spider now walks to the corner on the other end of the space diagonal using ...
2
votes
2answers
136 views

How to come up with One-To-One and Onto Examples

I'm trying to come up with example functions that are $N \rightarrow N$ for each category: One-to-one but not onto. Onto but not one-to-one. Nether one-to-one nor onto. Both one-to-one and onto. ...
2
votes
3answers
67 views

8 men and 8 women in a circle

There are 8 men and 8 women sitting in a circle. Prove that there are 8 adjacent people, so that 4 of them are men and 4 are women. (This is obvious, but how do I prove it?)
2
votes
1answer
55 views

Show that are logically equivalent [duplicate]

Show that are logically equivalent (without truth table) (p → r) ∧ (q → r) and (p ∨ q) → r My solution: ...
0
votes
3answers
49 views

Combinatorial problem - multisets

As I am solving some basic combinatorial problems today, I found out this problem: How many different 5-digit numbers can be formed from digits 2, 2, 7, 7, 9? Can someone guide me to a solution for ...
0
votes
0answers
60 views

Why this is a martingale?

Setup: $W$ probability space $Z_i : W \to L_i $ random variables ($L_i$ finite, for example $\{0,1\}$) $f: Z_1 \times \ldots \times Z_n \to \mathbb{R}$ $X_i := \mathbb{E}[f \mid Z_1,..,Z_i]$ Why ...
1
vote
1answer
35 views

Solving basic combinatorics

I started course in combinatorics and, as I'm still not much into it, I'm solving some basic problems to start with. So here is one of them: How many 5-digit positive integers are there such that 9 ...
0
votes
1answer
35 views

Show that are logically equivalent

Can you answer me , please. 1- Show that (p→r)∧(q→r) and (p∨q)→r are logically equivalent 2- show that (p → r) ∨ (q → r) and (p ∧ q) → r are logically equivalent without truth table .