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
43 views

Arranging $6$ distinct rooks on a $6\times 6$ board

How many ways there are to arrange $6$ distinct rooks on a $6\times 6$ board such that no rook would threaten another? My attempt: 1st rook: $36$ options. 2nd rook: $36-10+2=28$, there are 10 ...
0
votes
3answers
36 views

Proving Binomial using double counting

I was given this problem to prove in two different ways, but I am having trouble proving by the technique called Double Counting. We have to describe two counting procedures that count the same set. ...
0
votes
1answer
31 views

Confusion between conjunction and implication in a specific case

While writing following statement symbolically I ran into confusion. U is the set of all integers. 1) All the primes are non-negative let P(x) is used to express primes and N(x) for non negatives then ...
1
vote
2answers
30 views

What does “arrange all variables to range over one domain” mean?

In these notes (page 18, section 1.3.7) 1.3.7 Variables Over One Domain When all the variables in a formula are understood to take values from the same nonempty set, $D$, it’s conventional ...
0
votes
3answers
80 views

Lucas numbers and fibonacci

This is a question straight from the Applied Combinatorics book. Suppose that chairs are arranged in a circle. Let $L_n$ count the number of subsets of $n$ chairs which don't contain consecutive ...
0
votes
1answer
43 views

Proof by induction equation simplification

I am at the end of my proof, but don't know how from the left side obtain the right. equation: $\left[\dfrac{n(n+1)}{2}\right]^2 + (n+1)^3 = \left[\dfrac{(n+1)(n+2)}{2}\right]^2$ This is what I have ...
1
vote
1answer
76 views

Find the remainder when $78$ is divided by $11$.

Q) Find the remainder when 7 8 is divided by 11. ANS Here we define a%b is the remainder when we divide a by b. ...
2
votes
3answers
53 views

Give an example of four different subsets A, B, C and D of {1, 2, 3, 4} such that all intersections of two subsets are different.

My work, Suppose E={1,2,3,4} then power set of E is P(E)={ {}, {1}, {2}, {3}, {4} {1,2}, {2,3}, {3,4}, {1,3}, {1,4}, {2,4}, {1,2,3},{2,3,4}, {1,2,4}, {1,3,4}, {1,2,3,4} } Shows the possible subsets ...
0
votes
1answer
15 views

Discrete math question using PigeonHole

QUE: There are 30 students in the class where Jane is studying. In a Mathematics Test, Jane made 13 mistakes, any other student in the class made fewer mistakes. Use the generalized pigeonhole ...
1
vote
1answer
67 views

Why is one day in a discrete math problem taken as 100,000 seconds?

I have the following problem description and I am given several functions: "What is the largest n for which one can solve within a day using an algorithm that requires f (n) bit operations, where ...
2
votes
2answers
22 views

a, b, c, d are reals and a < b < c < d. express the set $[a,c] \cap [b, d]$ as difference of two intervals.

I'm struggling to solve the problem stated above. To help clarify the question I let a = 1, b = 2, c = 3,and d = 4. If that were the case then the interval I am interested is [b, c]. What does it ...
0
votes
0answers
38 views

How to determine a Big-O estimate for an algorithm

This question has been mentioned in the forum but with a different approach. I need to determine a Big-O estimate for the number of operations of the algorithm below taking into account only additions ...
-1
votes
1answer
46 views

How to prove the inductive step in this Mathematical induction problem?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 6, pg 342]. Problem: a) Determine which amounts of postage can be formed using just $3$-cent and $10$-cent ...
1
vote
1answer
18 views

Injective Function satisfying all certain domain

The function $f : \mathbb R \to \mathbb R$ satisfies $f(f(x)) − f(x) = x$. Is f injective? Why? Find all values of x such that $f(f(x)) = 0$. I think the function is one to one, though I am somewhat ...
3
votes
1answer
70 views

$\exists x P(x)\land\exists x Q(x)$ is not logically equivalent to $\exists x(P(x)\land Q(x) )$

The textbook states that the solution is: Let P(x) be "x is positive" and Q(x) is "x is negative". The domain is integers. This shows $\exists x P(x)\land\exists x Q(x)$ is True and shows ...
2
votes
2answers
34 views

How to come up with relation in induction hypothesis for strong induction

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, page 341]. Problem: Let $P(n)$ be the statement that a postage of n cents can ...
1
vote
1answer
46 views

Attempting a discrete proof: Not sure what I am doing wrong?

So this is an exercise that is a supplement to my studies in discrete math, I want to understand what my error is. The online training drill I am using reports the below is incorrect / or as we would ...
0
votes
2answers
35 views

Math Inequality using induction?

Prove that $\log_3\pi + \log_\pi 3 > 2$ without using log tables. I was thinking of using strong induction for something like this, but I find it a difficult thing to come by, especially giving ...
0
votes
1answer
68 views

How to show the inductive step of the strong induction?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 341]. Problem: Use strong induction to show that all dominoes fall in an infinite arrangement of dominoes if ...
1
vote
1answer
72 views

how to solve generating function for odd number?

im working on this question and i don't know where to start the question is: a) Find a closed form for the generating function $c(x)$ for counting compositions with $k$ parts, where each part is ...
0
votes
2answers
44 views

How to get $k^{k + 1} + k^k$ to equate $(k+1)^{k+1}$?

This is a problem from Discrete Mathematics and its Applications Let $P(n)$ be the statement that $n!<n^n$, where $n$ is an integer greater than $1$. $\quad(a)$ What is the ...
1
vote
2answers
36 views

Solve the linear system $x \equiv 12 \pmod{25}$ and $x \equiv 2 \pmod{30}$.

\begin{align*} x & \equiv 12 \pmod{25}\\ x & \equiv 2 \pmod{30} \end{align*} Hi guys, I'm not sure how to attack this problem. I know how to solve it if the moduli are coprime, but that ...
-1
votes
3answers
35 views

Unique Existential Quantifier

The Unique Existential Quantifier states that there exists a unique $x$ which holds for a $P(x)$. I came up with $$\exists x\;p(x)\land\neg\exists y\;p(y)\land x\ne y\;.$$ How is this different ...
1
vote
2answers
78 views

If a nonempty subset of integers is bounded from below, it has a minimum

Let $A$ be a non-empty subset of $\mathbb Z$. Suppose there exists $s \in \mathbb Z$ such that $s \le a$, for all $a \in A$. Show that $A$ has a minimum. I was assuming induction would be used ...
2
votes
2answers
29 views

Weak $k$-compositions with each part less than $j$

I am trying to figure out a problem from Richard Stanley's $\textit{Enumerative Combinatorics}$, which has to do with weak compositions of $n$ (sequence of nonnegative integers whose sum adds up to ...
0
votes
1answer
38 views

Harmonic summation

I am studying a few algorithms books at the moment, and I often see the harmonic summation come up. What I am confused about is, if the harmonic summation is: $$\sum_{i=1}^{n}1/i \sim \ln n$$ Why ...
1
vote
1answer
23 views

Elements in $X = \{2^n +1$ | $n$ is a positive integer and $2^n + 1$ is prime$\}$

Are $3, 5, 17$ and $257$ the first four elements in the set $X$? When I first wrote it out I thought it would be $1, 2, 4$ and $8$, but that doesn't seem right. I'm relatively new to set notation. ...
0
votes
1answer
51 views

Matrix equation: solving $AB(A^{-1})(D^T)(C-1 )= E$ for $D$

The question is: Assuming that all the following matrices are of the same size and nonsingular, solve $AB(A^{-1})(D^T)(C-1 )= E$ for matrix $D$. So far I got to $D^T = EC(B^{-1})$, but I do not know ...
-2
votes
2answers
39 views

prove that every lossless compression algorithm must result in increasing the file size for some inputs.? [closed]

Using Pigeonhole Principle prove that every lossless compression algorithm must result in increasing the file size for some inputs.?
0
votes
2answers
28 views

A is a proper subset of B implies NOT(B subset of A) Proof

This is not homework. I'm just studying for my Discrete Mathematics course. I'd like to know how to prove the following using element wise proofs: Given a proper subset: $$A \subset B \iff (A ...
1
vote
3answers
53 views

Solving recurrence equation with generating indices of positive indices [duplicate]

I don't know how to solve recurrence equation with positive indices like $$a_{n+2} + 4a_{n+1}+ 4a_n = 7$$ by generating functions. How to solve such kind of problems.
9
votes
2answers
494 views

when is $n!+10$ a perfect square?

When is $n!+10$ is a perfect square ? I have tried and found that only for $n=3$ is $n!+10$ a perfect square. Is there any other solution to this?
0
votes
2answers
24 views

Find the Quartile.

There are the following numbers from a sample data: $$36, 45, 49, 53, 55, 56, 59, 61, 62, 65, 69, 71, 76, 78, 81, 85, 91, 92, 99.$$ There are $19$ values. The question is to find the third quartile. ...
2
votes
3answers
80 views

Inductive proof, algebra step

I have to prove by induction that $$1^2+2^2+3^2+ \cdot \cdot \cdot + n^2 = {n(n+1)(2n+1)\over 6}$$ Base step: $$1^2 = {1(1+1)(2\bullet1 +1)\over 6}$$ $$1^2= {6\over 6} = 1$$ Then I use this ...
1
vote
1answer
35 views

Discrete Dynamical Systems & Credit Card Debt: How to solve for payment

I have the following problem, taken out of Giordano, Fox, and Horton's A First Course in Mathematical Modeling: Your current credit card balance is $\$12,000$ with a current rate of $19.9\%$ per ...
0
votes
3answers
28 views

Intersection and Union of Sets

If $A$ and $B$ are sets, find a condition on $A$ and $B$ such that $A \cup B = A \cap B$ if and only if $A$ and $B$ satisfy this condition. I think this means $A = B$, and that I have to prove that ...
0
votes
1answer
41 views

Will these rules hold for multi-sets (bags)?

I have proved that RHS = LHS, but I don't know whether that is what is being asked, or htey want something else. For example, for No. 2, I have proved the relationship like; $$ \begin{split} (R\cup ...
-1
votes
1answer
77 views

Assume that n is odd. Consider the following sum: $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{\frac{n-1}{2}}$ [closed]

Help i don't understand this question Assume that n is odd. Consider the following sum: $$ {n \choose 0} + {n \choose 1} + \cdots + {n \choose (n-1)/2} $$ (a) Write this sum using Riemann sum ...
0
votes
1answer
24 views

Clue about how to start solving a Big-Theta problem

I have been trying solve the following problem for some time and I just cannot find how to start. I will very much appreciate any feedback. Does Big-Theta(n^3 + 2^n + 1) = Big-Theta(n^3) hold? I have ...
1
vote
1answer
31 views

Find all positive integers $a$, $b$, and $c$ for which $a \choose b$ $b \choose c$ = 2$a \choose c$

Find all positive integers $a$, $b$, and $c$ for which $a \choose b$ $b \choose c$ = 2$a \choose c$. Using the theorem ${n! \over k!(n-k)!} = {n \choose k}$ I simplified this down to $(a-c)! = ...
2
votes
1answer
47 views

Distributing n identical balls in k distinct boxes

In how many ways can $20$ identical balls be distributed in $4$ distinct boxes, subject to the following conditions: Each box has at least $2$ balls, Each box has an even number of balls? The ...
2
votes
2answers
27 views

Proof alternating sum of squares is alternating sign of sum

I'm trying to prove by induction that $1-4+9-...\pm n^2 = \pm(1+2+...+n)$. The base-case is obvious, and the formula that I write this as is $$\sum_{i=1}^{n}(-1)^{i+1}i^{2} = ...
0
votes
0answers
26 views

determine the cardinality of $\{C \subseteq \mathbb N \space|\space \mathbb N - C \text{ is finite}\}$ [duplicate]

what is the cardinality of this set : $\{C \subseteq \mathbb N \mid \mathbb N - C \text{ is finite }\}$ So it must mean that $C$ is infinite, but even though its infinite we know how ...
0
votes
2answers
45 views

Computing the sum $\sum_{k=0}^{n} \binom{n}{k}(-1)^k(n-k)^n$

I need to compute $S_{n} = \sum_{k=0}^{n} \binom{n}{k}(-1)^k(n-k)^n$. $S_{2} = 2, S_{3} = 6,S_{4}=24$ therefore i think answer is $S_{n} = n!$. And i have got $S_{n}=(\Delta^n(n-x)^n)(0)$. But it ...
0
votes
1answer
42 views

Proof of an equation in functions

Consider a set of size $n$ like $\Omega =\lbrace 1,2,\cdots ,n\rbrace $, where $n$ is a positive integer. For every $x\in P(\Omega )$, define the function $f^x:P(\Omega )\rightarrow \lbrace \pm 1 ...
2
votes
1answer
36 views

What does a distributed lattice have to do with GCD and LCM?

$\newcommand{\lcm}{\operatorname{lcm}}$I am lost while following this explanation: Let $$A(g, i) = \gcd(F_{g}, \lcm(F_{a_1}, F_{a_2}, \ldots , F_{a_i}))$$ and $$X = \lcm(F_{a_1}, F_{a_2}, \ldots , ...
2
votes
1answer
19 views

How to find all possible polynomials over a given finite field?

How would I find the possible polynomials over GF(p)? I'm trying to figure out which polynomials of a specific given finite field have no roots.
0
votes
0answers
16 views

Multiset/Multinomial - Dividing Students into Teams

Question: I have 15 students and wish to divide them into three study teams of five students each. In how many ways can I do this? Is this not $\binom{15}{5,5,5}$, or am I missing something? I've ...
0
votes
1answer
48 views

Proving set properties?

I am stuck with proving that RHS = LHS. I don't know where to begin and how prove the questions below.
1
vote
3answers
35 views

Number theory problem! Prove the following using the method that relies on “Universal Generalization”.

If $n$ is the product of four consecutive integers then $n+1$ is a perfect square. Domain is all natural numbers What I got so far: Let $a$ be an element of natural numbers selected arbitrarily ...