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
0answers
2 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
-3
votes
2answers
29 views

List the elements of a set [on hold]

Consider the universal set $N$, $$A = \{m: m\ |\ 16\}$$ and $$B = \{n: n \le 16 \text{ and } n \equiv 17 \mod 3\}.$$ List the elements of A, list the elements of B.
1
vote
1answer
17 views

Proof By Induction $n^2 > 3n$ where $n\ge 4$

I am trying to prove the following example, however I seem to be getting a little stuck: For $n\in\mathbb N$, $n\ge 4, n^2>3n$ What I have Done: Base Case:$ n=4$, LHS: $4^2 = 16$, RHS: $3\cdot 4 ...
0
votes
0answers
6 views

Fast Fourier Transform Splitting Algorithm

I'm trying to figure out how the FFT splitting algorithm works. I've pretty much understood the general idea, but when I try to compute it, I get something completely different than what I expect $ ...
0
votes
2answers
25 views

Proving a property about modulus

I seem to be having a lot of trouble finding a place to start in proving that $$(a \cdot b) \mod m = ((a \mod m) \cdot (b \mod m)) \mod m$$ Any ideas on how I should go about doing this? I've been ...
0
votes
1answer
17 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
0
votes
0answers
18 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
0
votes
1answer
28 views

Gauss Method to show [on hold]

Could you please give me the way to solve this problem Using Gauss method to show if $x ≠ y + 1$ then $$ \sum_{i=0}^n (x-y)^i = \frac{(x-y)^{n+1}-1}{x-y-1}. $$
1
vote
1answer
22 views

Symbol clarification

Okay, so I've read a few different meanings for the exclamation point in a statement. For example: $$!\exists x \in O \ni 2x < 5$$ The only question I have is about the Exclamation point in front ...
-13
votes
0answers
69 views

Exist the proof of Goldbach's Conjecture… is it correct? [on hold]

Every even integer > 2 is the sum of two prime numbers & equivalent Each odd integer > 5 is the sum of three prime numbers USING THE SIEVE OF ERATOSTHENES ...
1
vote
1answer
13 views

What would the expected number of swaps in a merge sort be?

If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would ...
0
votes
0answers
58 views

The coefficients of $\frac{1}{\cos(x)}$ are even

Let's consider $G(z)=\dfrac{1}{\cos(z)}$ as an exponential generating function of the Euler numbers' sequence. How to prove that all $a_{i}$ in the expansion of$\dfrac{1}{\cos(z)}=\sum_{k=0}^{ ...
-1
votes
1answer
30 views

solving a recurrence without initial conditions

I have been working on this problem for two days... I can only get as the characteristic part of the recurrence, I just can't figure out a proper guess for the particular solution. ...
1
vote
1answer
20 views

Approach to determining if a graph is planar by inspection/kuratowski's theorem

I'm taking an intro discrete math course and am having trouble determining if a graph is planar or not. When proving a graph is planar, if Euler's formula doesn't apply I just randomly redraw the ...
0
votes
0answers
10 views

Possible configurations on the subset problem

Let $A=\left\{ a_{i}\right\} $ be a sequence of $n$ positive numbers such that $\sum a_{i}=1$. We define $C\left(A\right)=\left\{ \left\{ b_{i}\right\} \subset\left\{ 1,2..,n\right\} :\sum ...
1
vote
2answers
30 views

Complex infinity ($1/0$) [duplicate]

I've learned that $$1/0$$ is postive and negative infinity, but if I ask wolfram mathematica to calculate $$1/0$$ it gives me: 'complex infinity' but how can we proof that that is true?
-3
votes
0answers
34 views

PROVE : $y∈\mathbb{N}$ and $\sqrt{y} ∈ \mathbb{Q}$ then $\sqrt{y} ∈ \mathbb{Z}$ [on hold]

$ y∈\mathbb{N}$ and $\sqrt{y} ∈ \mathbb{Q}$ then $\sqrt{y} ∈ \mathbb{Z}$ Prove that, if $n$ is a natural number and $n$ has a rational square root then, the square root on $n$ is an integer.
2
votes
3answers
188 views

What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted ...
1
vote
2answers
19 views

Is transitive closure defined uniquely?

I'm encountering questions where I'm required to find a transitive closure (and the questions seem to suggest that there is only one), but I probably don't understand something in the definition, ...
-2
votes
3answers
40 views

Proving $6\mid A$ when $(x^3 +y) - (y^3 +x) = A$ [on hold]

Given that $x,y\in\mathbb{Z}$, prove that the difference between the expressions $(x^3 +y)$ and $(y^3 +x)$ is a multiple of $6$.
0
votes
0answers
13 views

Prove multivariable function is injective?

I am a little confused on how to prove a multivariable function is injective(one to one). I know the process for single variables but got stuck sadly. The function f: N -> N such that f((a,b)) = a^b ...
1
vote
2answers
26 views

What is the formula to find the number of one-one functions from A to B

let p = number or elements in A let q = number of elements in B if the number of functions from A to B is equal to q^p.... is their formula to find the number of one-one functions from A to B? how ...
1
vote
1answer
30 views

transitive closure and number of elements in relation?

I see an example as follows: in relation $R=\{(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a) \}$, on set $\{a,b,c,d,e,f\}$. we have $30$ elements in the transitive closure of $R$. How number of ...
0
votes
1answer
39 views

non-homogenous linear recurrence relation general questions

what happens if you have both repeated and non-repeated roots? i know there are different forms for both, so if given roots say $5, -3, -3, -3$ would it then be $A(5)^n + B(-3)^n + Cn(-3)^n + Dn^2 ...
1
vote
2answers
33 views

How to prove this recurrence [on hold]

Been stuck on this problem for a good while. Not sure how to approach it any help would be great! It is problem 12.
1
vote
1answer
22 views

Is it possible to reconstruct signal using phase only or magnitude only?

I am studying Fourier Transform and it's inverse. We get phase and magnitude from Fourier transform and reconstruct it back from both together My question is that is it possible to reconstruct given ...
0
votes
2answers
29 views

Help Showing a Relation is/isn't a Partial Order

Define the relation $\le$, as $(a,b)\le(c,d)$ if and only if $a+b\le c+d$ and $a\le c$. Is this a partial order? I know it's definitely not if we remove the $a\le c$ (because then it's not ...
-1
votes
0answers
12 views

p = X^2 and X = {a,b,c,d} [on hold]

Which ordered pairs need to be added to the universal relation p = X^2 on the set X = {a,b,c,d} to create the equivalence relation p* generated by p?
1
vote
1answer
18 views

Is a total order compatible with a partial order?

I was given the following multipart problem. Part 1: Consider the poset ({2,4,6,9,12,18,27,36,48,60,72},|), with the indicated integers and the divides relation. Find the following, if they exist; ...
0
votes
2answers
22 views

Is there a term for an “unbounded simplex”?

Is there a general term for regions like $\{(x,y):x>y\}$ and $\{(x,y,z): x>y>z\}$, i.e., regions which are simplexes with one open?
0
votes
1answer
29 views

4 cards are shuffled and placed face down. Hidden faces display 4 elements: earth, wind, fire, water. You turn over cards until win or lose.

Question: 4 cards are shuffled and placed face down in front of you. Their hidden faces display 4 elements: water, earth, wind, fire. You turn over cards until win or lose. You win if you turn over ...
0
votes
0answers
23 views

Partial Ordering and Hasse Diagram.

Draw the Hasse diagram for the partial ordering “x is a factor of y” on the following sets: S = {2, 3, 5, 7, 21, 42, 105, 210} I don't know how to find the partial ordering of this set. I know that ...
4
votes
4answers
58 views

Proving $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ for all $n\geq 1$ by induction

I'm practicing proofs by induction, and equalities seem to be the toughest for me. Can somebody please help to prove that for all integers $n \geq 1$: $$ 2^n -1 = \sum \limits _{i=0} ^{n-1} 2^i\;? $$ ...
4
votes
5answers
99 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...
-1
votes
0answers
24 views
0
votes
4answers
66 views

Proof by Induction $3^n > n^3$

I am trying to prove the following, however I'm stuck at the Induction hypothesis Prove by induction that, for all integers $n$, if $n\geq 5$, then $3^n>n^3$ What I have Done: Base Case: $n ...
-1
votes
1answer
32 views

Is this Event Mutally Exclusive?

I am trying to calculate the following, however I'm unsure on whether this event would be Mutally Exclusive or Independent. Can someone help with finding the probability of the Intersection? P(A) ...
-2
votes
0answers
36 views

question asks when is the birthday??? [duplicate]

Question asks how to find out Cheryl's birthday??
2
votes
1answer
27 views

Find generating functions for the Perrin and Padovan sequences

The Perrin sequence is defined by $a_0 = 3, a_1 = 0, a_2 = 2$ and $a_k = a_{k-2}+a_{k-3}$ for $k \ge 3$. The Padovan sequence is defined by $b_0 = 0, b_1=1, b_2=1$ and $b_k=b_{k-2}+b_{k-3}$ for ...
2
votes
2answers
45 views

Find the coefficient of $x^4$ in the expansion of $(1 + 3x + 2x^3)^{12}$?

I have not learnt the multinomial theorem yet, and was trying to approach this using the binomial theorem. I divided the terms as $a$ being $(1+3x)$ and $b$ being $2x^3$. I then used $${12\choose ...
1
vote
2answers
41 views

Summation Proof Dealing With 3s Multiples [duplicate]

So the problem is as follows: Prove that if the sum of digits of a decimal $n$ is three's multiple, then n is three's multiple by direct proof. For example, $11234567$ is 3's multiple because ...
3
votes
2answers
39 views

Multiple part problem concerning the proof that $\sum_{k=1}^n k^3=\left(\frac{n(n+1)}{2}\right)^2$ by induction

So I'm having trouble with $c,d$ and $e$. For $c$ so far I have: Inductive Hypothesis: $(\frac{n(n+1)}{2})^2 = (\frac{(k+1)(k+2)}{2})^2$ is that correct?
-1
votes
0answers
27 views

Combinatorics: Password consisting of 13 characters. Must contain at least one odd digit, and at most two even digits. How many passwords?

I'm really trying here. I just need help where to go next. Each character is one of the 10 digits 0, 1, 2, ... , 9 What I have so far is that there are 10^13 possible passwords. I'd have to subtract ...
-2
votes
0answers
48 views

Summation Direct Proof Help [on hold]

Prove that if the sum of digits of a decimal n is three's multiple, then n is three's multiple by direct proof. For example, 11234567 is 3's multiple because 1+1+2+3+4+5+6+7=24, and in fact, 11234567 ...
1
vote
1answer
23 views

Derive an exact formula (solve the recurrence definition) for the following recursive sequence:

Derive an exact formula (solve the recurrence definition) for the following recursive sequence: $s_n = 2_{s_n-1} - s_{n-2}$ where $n \ge 2$, and $s_0 = 4$, $s_1 = 1$. So I saw someone solving this by ...
1
vote
2answers
37 views

Proving $10^n \equiv 1 \pmod 3$ for all $n\geq 1$ by induction

Prove that $10^n \equiv 1 \pmod 3$ for all positive integers $n$ by mathematical induction. Can someone please help me in solving this problem and explain what's going on? Any guidance would be ...
2
votes
1answer
51 views

Combinatorics Question VS CS solution!

I was wondering for some conceptual understanding to a question of this form: In how many ways may we choose three distinct integers from [1, 2, ..., 80] so that one of them is the average of the ...
1
vote
2answers
28 views

Verify that $\alpha(a)\neq2$ for all $a$ where $\alpha(x): (2x + 1)/(x + 2)$

If $A= \mathbb{R} \setminus \{-2\}$ and $B = \mathbb{R} \setminus \{2\}$, let $\alpha: A \to B$ by $\alpha(x): (2x + 1)/(x + 2)$. Verify that $\alpha(a)\neq2$ for all $a \in A$. As a hint, I was ...
3
votes
3answers
38 views

You are making cookies and add N chips to dough randomly, and split it into 100 equal cookies, again at random. How many chips should go into dough?

Question: You are making chocolate chip cookies. You add N chips randomly to the dough and you randomly split the dough into 100 equal cookies. How many chips should go into the dough to give a ...
-4
votes
3answers
76 views

Proving that $2^n+1\leq 3^n$ by induction

I need to prove the following using mathematical induction: $$2^n+1\leq 3^n\qquad\forall n\in\Bbb{Z^+}$$ Been working on this problem for a while and cannot figure it out. Any guidance or help would ...