Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

5
votes
3answers
1k views

Domain, codomain, and range

This question isn't typically associated with the level of math that I'm about to talk about, but I'm asking it because I'm also doing a separate math class where these terms are relevant. I just want ...
5
votes
5answers
6k views

How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I ...
5
votes
2answers
247 views

Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?

My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
5
votes
5answers
3k views

Calculate number of small cubes making up large cube given number in outermost layer

I have a large cube made up of many smaller cubes. Each face of the cube is identical, and all of the smaller cubes are identical. I need to calculate the number of small cubes that make up the large ...
5
votes
3answers
314 views

Is “$n$ is an integer and $\frac{n}{n+1}$ is an integer” true or false?

I am working through a suggested exercise "If $n$ is an integer, $\frac{n}{n+1}$ is not an integer" - I can prove this is false, and I can prove the converse is false, and I can prove the ...
5
votes
4answers
102 views

How to prove that if $2x^2-x=2y^2-y$, then $x=y$, for $x,y\in\mathbb{Z}.$

How to prove that if $2x^2-x=2y^2-y$, then $x=y$, for $x,y\in\mathbb{Z}.$
5
votes
5answers
145 views

Help understanding $x=y\Rightarrow(x=z\Rightarrow y=z)$

I was reading a proof that opened with the integer axiom of $x=y\Rightarrow(x=z\Rightarrow y=z)$ What would be an accurate statement in English to express this? The "implies" within the first ...
5
votes
4answers
361 views

What exactly are equivalence classes

What exactly are equivalence classes? Suppose I have an equivalence relation $\sim$ on some set $X$ we denote this as $x \sim y$. The equivalence classes are then $[x] = \{y \in X : y \sim x\}$. ...
5
votes
3answers
242 views

Generating Functions- Closed form of a sequence

We are given the following generating function : $$G(x)=\frac{x}{1+x+x^2}$$ The question is to provide a closed formula for the sequence it determines. I have no idea where to start. The denominator ...
5
votes
3answers
167 views

Comparison of 2 sets and the '+' operator in set theory

I would like clarification on a set theory question I have. The question reads: Suppose $X$, $Y$ and $Z$ are sets: Does $X \times (Y +Z)=(X\times Y)+(X\times Z)$ (Where $\times$ is the cartesian ...
5
votes
1answer
185 views

How to solve this recurrence relation $a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$?

I am trying to solve the recurrence: $$ a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}} $$ but here is a problem for me. After few steps I have this: $$ a_n^2 = a_{n-1}\cdot a_{n-2} $$ and I don't now what to do ...
5
votes
4answers
208 views

How would you solve this recurrence equation: $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$

How would you solve $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$ ? I don't understand the text in my textbook. I Would like somebody to explain it to me.
5
votes
3answers
749 views

Analysis of Algorithms: Solving Recursion equations-$T(n)=3T(n-2)+9$

I need your help with solving this recursion equation: $T(n)=3T(n-2)+9$. with the initial condition : $T(1)=T(2)=1$. I need to find $T(n)$, the complexity of the algorithm which works that way. I ...
5
votes
3answers
336 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
5
votes
2answers
199 views

Showing one set is a subset of another

Let's say you have sets $A,\, B,$ and $C.$ How would you show that $[(A-B) - C]\subseteq (A-C)$ using a venn diagram or logical translations? How can this even be done when you don't know the ...
5
votes
2answers
505 views

A wheel has the numbers 1 to 25 randomly placed on it. Show that there are three adjacent numbers whose sum is at least 39.

Any thoughts on understanding how to do this using the Principle of Mathematical Induction would be great. A wheel of fortune has the integers from 1 to 25 placed on it in a random manner. Show that ...
5
votes
2answers
330 views

Proof that no polynomial with integer coefficients can only produce primes

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
5
votes
3answers
4k views

Odd/Even Permutations

How do you classify a permutation as odd or even (composition of an odd or even number of transpositions)? I somewhat understand the textbook definition of it but im having hard time conceptualizing ...
5
votes
3answers
196 views

Interesting tea-time problem

Problem A: Please fill each blank with a number such that all the statements are true: 0 appears in all these statements $____$ time(s) 1 appears in all these statements $____$ time(s) 2 appears in ...
5
votes
1answer
247 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...
5
votes
3answers
627 views

Could someone please explain to me how (p ∨ q) = (p NAND p) NAND (q NAND q)

I can prove it all the way to: What is the proof for those two equaling? So far I have: (p ∨ q) = (p ^ p) ∨ (q ^ q) Negate it… ~((p ^ p) ∨ (q ^ q)) You get… ~(p ^ p) ^ ~(q ^ q) = (p NAND p) ^ ...
5
votes
3answers
383 views

How can I count the number of colored combinations in a set of regions?

Let me first start out by saying as you might have guessed, this is a homework problem. Therefore I am not looking for an answer to the question. I am looking for help in how to analyze it (My ...
5
votes
1answer
158 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
5
votes
1answer
211 views

Pigeon Hole Problem

Prove that of any 100 different twelve digit numbers (first digit cannot be zero) there are two of them with the same first and fifth digit. I'm new to this principle and need some assistance. I've ...
5
votes
2answers
203 views

I need to disprove an alternate definition of an ordered pair. Why is $\langle a,b\rangle = \{a,\{b\}\}$ incorrect?

So we know that the an ordered pair $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$. And we know the Kuratowski definition of an ordered pair is: $(a,b) = \{\{a\},\{a,b\}\}$ ...
5
votes
3answers
182 views

How can one simplify $¬(¬∃x, P(x)) $ and $\neg(\neg\forall x,P(x))$?

What I've learned so far: $\lnot$($\forall$$x$, P($x$)) $=$ $\exists$$x$, $\lnot$P($x$) $\lnot$($\exists$$x$, P($x$)) $=$ $\forall$$x$, $\lnot$P($x$) So far so good (I hope!) But what about ...
5
votes
2answers
205 views

Combinatorial explanation to following recurrence relation $a_n = 2 a_{n-1} + a_{n-2}$

Question was the following: $a_n$ is the number of ternary strings (strings of 0,1,2) which contain no consecutive zeros and no consecutive ones. Find a formula for $a_n$? By brute force, I found a ...
5
votes
3answers
107 views

Closed formula for linear binomial identity

I have the following identity: \begin{equation} m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1} \end{equation} I solved for the values and learned of the interpretation of W, X, Y, and ...
5
votes
2answers
754 views

How many $n$-digit palindromes are there?

How can one count the number of all $n$-digit palindromes? Is there any recurrence for that? Thanks. I'm not sure if my reasoning is right, but I thought that for n=1 we have 10 such numbers ...
5
votes
2answers
190 views

Show $ 1 + a + a^2 + a^3 + \ldots + a^n = \frac{a^{n+1}-1}{a-1}$ by induction

How can we show by mathematical induction that the following holds for $ n \ge 0$ and $a \ne 1$? $$ 1 + a + a^2 + a^3 + \ldots + a^n = \frac{a^{n+1}-1}{a-1}$$ I understand the principle of ...
5
votes
2answers
330 views

Fibonacci Number Proof

How can I prove this statement? Would I use induction? "Given $n \geq 11$, show that $a_n > (3/2)^{n}$. $a_n$ is the $n$th Fibonacci number."
5
votes
3answers
367 views

Proving an equality involving compositions of an integer

Let's consider various representations of a natural number $n \geq 4$ as a sum of positive integers, in which the order of summands is important (i.e. compositions). The task is to prove the number ...
5
votes
2answers
264 views

Evaluating complicated sum

Evaluate for a fixed $m\neq 1$ ( $m\in \mathbb{N}$ ) $$\sum _{k=1}^{n}\left[\left( \sum _{i=1}^{k}i^{2}\right) \left(\sum _{k_{1}+k_{2}+...+k_{m}=k}\dfrac {\left( k_{1}+k_{2}+\ldots +k_{m}\right) ...
5
votes
2answers
2k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...
5
votes
3answers
673 views

How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing? The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?
5
votes
2answers
157 views

On the Definition of Posets…

In my book, the author defines posets formally in the following way: Let $P$ be a set, and let $\le$ be a relationship on $P$ so that, $a$. $\le$ is reflective. $b$. $\le$ is transitive. $c$. ...
5
votes
1answer
243 views

How to begin Combinatorial Proof

The question states to give a combinatorial proof for: $$\sum_{k=1}^{n}k{n \choose k}^2 = n{{2n-1}\choose{n-1}}$$ Honestly, I have no idea how to begin. I want to do a two-way counting proof, ...
5
votes
3answers
228 views

Number of point subsets that can be covered by a disk

Given $n$ distinct points in the (real) plane, how many distinct non-empty subsets of these points can be covered by some (closed) disk? I conjecture that if no three points are collinear and no four ...
5
votes
3answers
138 views

Looking for a function $f$ such that $f(i)=2(f(i-1)+f(\lceil i/2\rceil))$

I'm looking for a solution $f$ to the difference equation $$f(i)=2(f(i-1)+f(\lceil i/2\rceil))$$ with $f(2)=4$. Very grateful for any ideas. PS. I've tried plotting the the initial values into ...
5
votes
3answers
151 views

How many ways can 5 dice produce a total of 20?

How many ways can $5$ dice produce a total of $20$? I set up the equation $x_1+x_2+x_3+x_4+x_5 = 20$. The total possible number of combinations is $\binom{19}4$. From there I subtracted the ...
5
votes
2answers
86 views

Discrete math logic question

I have the following two questions. For all real numbers x, there is a real number y such that $2x+y=7$ would this be true or false? I think true because if you put $2(7)+y=14$ $2(8)+y=14$ there ...
5
votes
4answers
269 views

Prove or disprove the following statements involving greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
5
votes
1answer
88 views

Proving at least 99 pairwise sums of the reals are non-negative

Suppose, one hundred real numbers are given and their sum is 0.Then how can I prove that at least 99 of the pairwise sums of these hundred numbers are non-negative? I tried this: Let the real numbers ...
5
votes
2answers
2k views

Prove or disprove: if A is a subset of B and B is not a subset of C, then A is not a subset of C

Prove or disprove: if A is a subset of B and B is not a subset of C, then A is not a subset of C. I know it is false for the counter example: A = {1, 2} B = {1, 2, 3, 4} C = {1, 2, 6, 5} How ...
5
votes
2answers
330 views

Symbolic coordinates for a hyperbolic grid?

Rephrasing     (one year later)    (original question is below) Apparently the original question wasn't clear, or nobody knows an answer (or both). So I will try to rephrase it. Look at your ...
5
votes
2answers
3k views

Expected number of runs in a sequence of coin flips

A coin with heads probability $p$ is flipped $n$ times. A "run" is a maximal sequence of consecutive flips that are all the same. For example, the sequence HTHHHTTH with $n=8$ has five runs, namely H, ...
5
votes
3answers
361 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
5
votes
2answers
66 views

Alternate translation for: “Every real number except zero has a multiplicative inverse.”

A given text states, “Every real number except zero has a multiplicative inverse" (where mul- tiplicative inverse of a real number x is a real number y such that xy = 1). It offers the following ...
5
votes
2answers
92 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
5
votes
1answer
57 views

Writing in 1993, a researcher noted that it is hard to prove things about a cellular automata model - has this changed?

Leah Edelstein-Keshet in her 1993 article Cellular automata approaches to biological modelling writes: We do not believe that CA should be viewed as a replacement for rigorous mathematical models. ...