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

learn more… | top users | synonyms

5
votes
5answers
5k 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
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
143 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
357 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
240 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
163 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
184 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
734 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
332 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
193 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
499 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
308 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
194 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
243 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
602 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
375 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
157 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
210 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
196 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
178 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
201 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
106 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
689 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
188 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
320 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
362 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
256 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
150 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
238 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
4answers
268 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
320 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
1answer
55 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. ...
5
votes
2answers
144 views

generating function for binary strings that don't contain $00100$ as a substring?

On an alphabet $\{0, 1\}$, what's the generating function for the set of strings that don't contain $00100$ as a substring? I've tried writing the set of strings that don't contain $00100$ in terms of ...
5
votes
2answers
726 views

How many 9 letter strings are there that contain at least 3 vowels?

I'm studying for my exams and stuck on this one question. The way I'm thinking of doing this is by: $$26^9 - \binom{26}3-\binom{26}2-\binom{26}1-\binom{26}0= 5,429,503,676,728$$ But that seems ...
5
votes
2answers
161 views

Sipser Pumping Lemma Clarification

In a Theory of Computation book I am using, the explanation of Pumping Lemma is not bad, but some parts of it are not clear to me. Here is the Definition of Pumping Lemma: If A is a regular ...
5
votes
3answers
295 views

Are these two 10-vertex graphs isomorphic?

Explain if these two graphs are isomorphic. If so, give the 1-1 correspondence of nodes. I've checked that the two graphs have the same degrees, edges, and vertices, and check that they both aren't ...
5
votes
1answer
777 views

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions…Induction!

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point. I know we start with the base case, where, ...
5
votes
4answers
3k views

What is the solution to the following recurrence relation with square root?

This looks like a question asked earlier, but it isn't T(n) = T (sqrt(n)) + 1 ... if n>1 =1... if n=1 My professor gave this to me in class yesterday. This is where I'm stuck.. T(n) ...
5
votes
1answer
337 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
5
votes
1answer
313 views

Prove parity of binomial coefficient

The task is to find the parity of ${2n\choose 2k+1}$ where $n,k\in\mathbb{N}$. How can I do that?
5
votes
1answer
1k views

Asymptotics for a partial sum of binomial coefficients

Good afternoon, I would like to ask, if anyone knows how to evaluate a sum $$\sum_{k=0}^{\lambda n}{n \choose k}$$ for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better. In ...
5
votes
3answers
242 views

Formula for sums of rows of a “triangle” of arithmetic progressions

Due to my lack of mathematical training, I'm having a hard time phrasing this question, so please bear with me. Let '$a_{(1,j)}$' define the following series: $a_{(1,1)}=1$, ...
5
votes
1answer
190 views

Inverse, Converse and contraposition of statement?

I am trying to break the statements: "Being rich is necessary for Alex to be happy"(1) and "Stop, or I will shoot!"(2) (1) Statement $\neg Rich \Rightarrow \neg Happy$ Converse $\neg Happy ...
5
votes
3answers
157 views

Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$

Bring the following recursion relation to an explicit expression: $$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$ $a_{0} = 0$, $a_1 = 1$, $a_2 = 2$ All the examples I have seen were with maximum 2 steps back ...