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

learn more… | top users | synonyms

7
votes
5answers
439 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, ...
7
votes
2answers
835 views

How many bins do random numbers fill?

Given is a sequence $\langle a_1,a_2,\ldots,a_n\rangle$ over the alphabet $\{1,2,\ldots,m\}$ chosen uniformly at random among the $m^n$ possibilities. What is the expected size of the set ...
7
votes
4answers
259 views

Not understanding the concept of equivalence class

Let $U$ be a set defined: $U=\{(x,y)\in \Bbb R^2\mid x^2+y^2=1; xy\neq 0\}$, and let $R$ be relation defined: $(x_1,y_1)R(x_2,y_2) \iff (x_1 \cdot x_2>0∧y_1\cdot y_2>0)$. I was to prove it's ...
7
votes
4answers
547 views

Closed-form expressions for sums

I've got a problem with deducing closed-form expressions for sums: $1) \ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ $2) \ \sum_{A,B\subseteq X} |A\cup B|$ where $|X|=n$ Can anyone help me? ...
7
votes
2answers
323 views

Given three integers in $\{0,\ldots,100\}$ which sum up to $100$. What is the probabilty that two of them are the same?

We pick $3$ numbers (one by one) from set $\{0,1,...,100\}$. What is probabilty that two numbers are the same if sum of those $3$ numbers is $100$? My solution: Which two are the same we can pick in ...
7
votes
2answers
404 views

Visualizing Concepts in Mathematical Logic

If you were forced to speculate or offer anecdotal evidence, how would you say excellent practicioners of mathematical logic coneptually grasp statements like: $$ \vdash ((P \rightarrow Q) ...
7
votes
2answers
369 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
7
votes
1answer
239 views

Spectrum of a real number

Whilst reading Concrete Mathematics, the authors mention something which they refer to as the "spectrum" of a real number (pg. 77): We define the spectrum of a real number $\alpha$ to be an ...
7
votes
2answers
125 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
7
votes
2answers
296 views

Existence of infinitely many integers $n$ such that $2^n$ ends with $n$

Can anyone please help me on the following proof: Prove that there exist infinitely many positive integers $n$ such that $2^n$ ends with $n$ in decimal notation, i.e. $2n = \ldots n$.
7
votes
3answers
582 views

Cardinality of a discrete subset

If I am correct, a discrete subset of a topological space is defined to be a subset consisting of isolated points only. This is actually equivalent to that the subspace topology on the subset is ...
7
votes
4answers
1k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in ...
7
votes
2answers
211 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
7
votes
3answers
586 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
7
votes
2answers
438 views

If we have $m$ indistinguishable objects how many ways is it possible to put them in $n$ indistinguihable positions?

if we have $m$ indistinguishable objects, how many ways is it possible to put them in $n$ indistinguishable positions? (for 2 cases 1: without empty position allowed 2: empty positions are allowed.) ...
7
votes
1answer
97 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
7
votes
1answer
90 views

Number of permutations $\langle a_1,\ldots,a_n\rangle$ of $\{ 1,\ldots ,n \}$ with $a_{i+1} - a_i \ne 1$

Prove that for $n>0$, the number of permutations $\langle a_1,\ldots,a_n\rangle$ of the set $\{ 1,\ldots ,n \}$, where $a_{i+1} - a_i \ne 1$ for $ i = 1, \ldots, n-1$ is equal to: $$D_n + ...
7
votes
1answer
130 views

Graph, two colors, no path length 3

I've just begun studying graph theory and I have some difficulty with this problem. Could you tell me how to go about solving it? In a graph $G$ all vertices have degrees $\le 3$. Show that we can ...
7
votes
3answers
185 views

Changing Summation Index Question

I'm sorry if this seems like a very novice question, but I am still relatively new to the world of discrete math ( still in 9th grade). I've been reviewing some of the concepts I learned in a ...
7
votes
1answer
3k views

How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$ This is what I've already done: $$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$ $$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$ ...
7
votes
1answer
128 views

For how many $n \in \mathbb{N}$ is $\sqrt{n^2+2379}$ natural?

Here's my attempt at a solution: the expression $\sqrt{n^2+2379}$ is natural iff $$n^2 + 2379 = x^2, \quad \mbox{ for some } x \in \mathbb{N}.$$ Therefore $$(x+n)(x-n)=2379=3 \cdot 13 \cdot 61.$$ I ...
7
votes
2answers
399 views

A magic trick with synchronizing words

See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html Spoiler Alert Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
7
votes
2answers
198 views

Combinatorial proof for identity $\left(\!\!\binom{n\vphantom{1}}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right)$ (multiset coefficients)

In class we have recently started using combinatorial proofs. I have tried this problem that our teacher has assigned as a "challenge". I understand how to receive the left hand side, but am ...
7
votes
1answer
137 views

Equation $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$

I think this equality is very inters prove that: $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$
7
votes
1answer
150 views

Connecting cells by line and column permutations in a finite grid

I'd like to know whether the following simple problem has been studied before and if any solution is known. Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said ...
7
votes
1answer
83 views

Prove this is an equivalence relation.

Define a relation of $\mathbb{Q} -$ {$0$} as follows: $x$ ~ $y$ $\Leftrightarrow$ $\dfrac {x} {y} = 2^k $ for some $k \in \mathbb{Z}$ Prove this is an equivalence relation. ATTEMPT: Reflexive: ...
7
votes
0answers
221 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
7
votes
0answers
177 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
7
votes
0answers
172 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
7
votes
0answers
151 views

A variation on the Look and Say Sequence and some questions about it.

For information on the sequence mentioned in the title, see http://en.wikipedia.org/wiki/Look-and-say_sequence. This is an original problem. Suppose instead of "describing" the numbers in a string in ...
7
votes
0answers
431 views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
6
votes
3answers
829 views

Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

This is on Lagrange Interpolations . . . Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23? The hint that he gave us is to use Summation Products, the only ...
6
votes
3answers
953 views

Shortest solution to order 26 alphabet letters, no two vowels occurring consecutively

What is the shortest solution to the following problem? What is the number of ways to order the 26 letters of alphabet so that no two of the vowels a,e,i,o,u occur consecutively? What I ...
6
votes
3answers
148 views

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$?

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$? Can someone elaborate on this a bit?
6
votes
1answer
202 views

Show the distance does not exceed $\sqrt{2}$.

Choose any ten points from the interior of a square with side length $3$. Show that the distance of some pair of these points does not exceed $\sqrt{2}$. Can someone help me?
6
votes
5answers
833 views

discrete math book suitable for younger person?

When I took discrete math as an adult I realized that this was a subject I would have enjoyed and done well at much earlier in life, even in my early teens. Does anyone know if there are good books, ...
6
votes
4answers
262 views

How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

I need to solve the problem, How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$? I've been given a hint, (Hint: Reduce the ...
6
votes
3answers
130 views

Help with math induction

Prove that $n(n+1)(n+2)$ is divisible by $6$ for all integers. I'm not sure if I'm suppose to use division into cases or not. Our teacher ran out of time to go over this in class, and this is on ...
6
votes
2answers
320 views

Watchdog Problem

I just came up with this problem yesterday. Problem: Assume there is an important segment of straight line AB that needs to be watched at all time. A watchdog can ...
6
votes
3answers
196 views

How many 3-subsets of $\{1,2,\ldots,10\}$ contain at least two consecutive integers?

Let A = {1, 2,..., 10}. How many three-element subsets of A contain at least two consecutive integers? I believe there are $\displaystyle \tbinom{10}{3}$ total 3-subsets of A. To find the subsets ...
6
votes
5answers
418 views

trivial but non-trivial equivalence relations

Define a binary relation $R$ on a set $A$ by saying $xRy$ iff $x$ and $y$ have the same whatever. "Whatever" is of course some specified function on $A$. This is a "trivial" equivalence relation: ...
6
votes
5answers
2k views

If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors.

I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese) A plane is divided by many lines. Show that it is possible to color the regions formed with only two ...
6
votes
3answers
68 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
6
votes
1answer
231 views

Recurrence relation satisfied by $\lfloor(1+\sqrt{3})^n\rfloor$

This is a follow up to a question I had asked earlier about a linear recurrence relationship satsified by $\lfloor(1+\sqrt{5})^n\rfloor$. I messed up there, and I actually meant to ask about ...
6
votes
2answers
263 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
6
votes
3answers
146 views

Why is the function $f(x)=x^3 \pmod{10}$ periodic with this strange property?

I've noticed that the function $f(x)=x^3 \pmod{10}$ is periodic. For example, listing mod(x^3,10) we get: ...
6
votes
3answers
657 views

Looking for induction problems that are not formula-based

I am looking for problems that use induction in their proofs such as this one: Given a checker board with one square removed you can cover it with L-shaped pieces made out of three squares. This ...
6
votes
3answers
4k views

Transitive Relations

For example, $$R = \{ (1,1),(1,2),(2,1),(2,2) \} \quad\text{for}\quad A = \{1,2,3\}.$$ This relation is symmetric and transitive. I understand that the relation is symmetric, but my brain does not ...
6
votes
3answers
3k views

Inclusion-exclusion principle: Number of integer solutions to equations

The problem is: Find the number of integer solutions to the equation $$ x_1 + x_2 + x_3 + x_4 = 15 $$ satisfying $$ \begin{align} 2 \leq &x_1 \leq 4, \\ -2 \leq &x_2 \leq 1, \\ 0 \leq ...
6
votes
2answers
85 views

Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$

I need to find a clear formula (without summation) for the following sum: $$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$ Well, the first few elements look like this: $1,1,1,2,2,2,2,2,3,3,3,...$ ...