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

learn more… | top users | synonyms

2
votes
1answer
188 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...
1
vote
1answer
23 views

Discrete dynamic models

We have the equation $$x_{n+1} = ax_n(1-x_n) - v_n$$ Why are there only fixed points for $(a-1)^2 - 4av_0 \geq 0$? Show that if $ 1<a<4$, there are 2 fixed points with $0<p_1 < p_2 ...
3
votes
2answers
81 views

$ k x^2 +4x = n $, Algorithm or any other method needed

I want to find any $n < 10^{18} $ so that the equation below has at least two pairs of solutions $(k, x)$ $ k x^2 +4 x = n $ constraints: $x > 10^6; \; x > k ; \; k, x \in \mathbb{N}$ I ...
36
votes
26answers
3k views

How to teach mathematical induction?

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of ...
0
votes
1answer
312 views

Principle of Inclusion and Exclusion

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people, 21 bring hot dogs, 35 bring fried chicken, 28 ...
1
vote
4answers
85 views

congruence proof: Prove that there is no integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true.

Prove that there is no Integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true. How should I approach this question? I attempted using contra-positive proof, so $x=6p+2$ and $x=9q+3$ ...
4
votes
3answers
384 views

17! mod 13, How do I do this without a calculator

So I know $$17! = 17 \times16\times15...\times1$$ So I was thinking maybe go $$17mod(13)\equiv4 \space \space and \space 16mod(13)\equiv3 ...$$ add all that together but that is too much work so I ...
0
votes
1answer
54 views

how to work out $14^{293}-12^{26}\pmod{13}$

How can I work this out without a calculator? $$14^{293}-12^{26} \pmod{13}$$ I just couldn't figure out a way to do this.
1
vote
1answer
85 views

Probability, making a selection of 5 people from 10, with two married couples with restrictions

10 people. must make a committee of 5 people So the restrictions are 1) Mr and Mrs Q can't be separated 2) Mr and Mrs P can't be in the same committee. So how many possible committees ...
2
votes
2answers
109 views

Why does the Tower of Hanoi problem take $2^n - 1$ transfers to solve?

According to http://en.wikipedia.org/wiki/Tower_of_Hanoi, the Tower of Hanoi requires $2^n-1$ transfers, where $n$ is the number of disks in the original tower, to solve based on recurrence relations. ...
0
votes
2answers
118 views

Representative choices of four out of eleven students with three majors

I am majoring in philosophy and currently im taking a logic course. I am having trouble with this question and I think you all mathematicians could help me out. There are five philosophy majors, four ...
2
votes
1answer
60 views

Finding a generating function of a series

So say if you have a sequence defined as, for $a\in\mathbb{Z}$, $$ c_n = \binom{a}{0} \binom{a}{n} - \binom{a}{1} \binom{a}{n-1} + \cdots+ (-1)^n \binom{a}{n} \binom{a}{0} = \sum_{i=0}^n (-1)^i ...
1
vote
0answers
58 views

counting more problem continue [duplicate]

i have asked but no one was able to help so i am re-posting, hoping someone can help me. i did the computation and i could be wrong but i have provided my answer. Given problem: How many ways can 5 ...
3
votes
2answers
52 views

counting another problem

I am trying to do my homework and it seems really hard. i would like to get checked here and make sure that im on the right track. can anyone help me?? Question: A group of hundred students want to ...
1
vote
1answer
53 views

Proof convex polyhedron with line does not contain a corner if closed

The excercise I am struggling with is the following: Given a convex closed polyhedron that contains a line, the question is, whether this polyhedron can also contain a corner. My idea was to make a ...
4
votes
1answer
88 views

Evaluate complicated sum

Evaluate following sum: $$\sum_{1\leqslant i< j \leqslant m}\sum_{\substack{1\leqslant k,l \leqslant n\\ k+l\leqslant n}} {n \choose k}{n-k \choose l}(j-i-1)^{n-k-l}.$$ Hint: use combinatorial ...
1
vote
3answers
96 views

$3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. Is my induction solution correct?

Show using mathematical induction that $3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. I'm not sure whether what I did at the last is valid? Basis step: for all non-negative integers ...
1
vote
3answers
59 views

What do you use for your basis step when its domain is all integers?

Example: *For all integers $ n , 4( n ^2 + n + 1) – 3 n ^2$ is a perfect square what should i use? negative infinity? I know you can use a direct proof but what if theres an induction question with ...
1
vote
0answers
44 views

Edge in a convex polytope

I want to show that a convex polytope $A$ that is an intersection of half-spaces contains an edge if $ A=\{x \in \mathbb{R}^n|Ax=0 \wedge x \ge 0\}$, where x greater equal 0 means, that all components ...
0
votes
3answers
4k views

Venn diagram problem solving question

In a class of $63$ students, $22$ study biology, $26$ study chemistry and $25$ study physics. $18$ study both physics and chemistry, $4$ study both biology and chemistry and $3$ study both physics and ...
3
votes
2answers
229 views

Counting donut problems

By using the permutation and combination techniques, i have attempt to solve this problem and i would like to know if where i did it wrong how many ways to choose $12$ donuts from a store that offers ...
1
vote
3answers
113 views

Permutations and combinations on letters

I have given a few problems and i have been using the permutation and combination to solve the problems. However, i am suck at counting. but i do my best though. So, im here to ask a question. how ...
0
votes
2answers
156 views

Probability density/mass function

I am a bit confused as to the difference between the probability mass function and the probability density function for a distribution of discrete variables. I understand there would be no mass ...
0
votes
1answer
43 views

Relation between stirling numbers

Is there a relation between $$ \genfrac\{\}{0pt}{}{n}{n-2} $$ and $$ \genfrac\{\}{0pt}{}{n-1}{n-3} $$ Like the first one can be obtained from the second one by adding something?
-3
votes
1answer
83 views

Can someone help me solve this problem please. [duplicate]

For the real numbers $x=0.9999999\dots$ and $y=1.0000000\dots$ it is the case that $x^2<y^2$. Is it true or false? Prove if you think it's true and give a counterexample if you think it's false.
3
votes
1answer
127 views

Closed formula for number of $n$ distinct topologies

While studying some topoligies I asked myself how many distinct topologies exist on a set of $n$ points. It can be shown there is a relation to $T_0$ topologies and a formula for $n$ distinct ...
2
votes
1answer
45 views

Stirling numbers with $k=n-2$

Is there a more general method of calculating: $$ \genfrac\{\}{0pt}{}{n}{n-2} $$ Like for :$$ \genfrac\{\}{0pt}{}{n}{n-1} $$ we can use $nC_2 $
5
votes
2answers
506 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 ...
3
votes
1answer
373 views

Concrete Mathematics Prerequisite Question

I've been very interested in the book Concrete Mathematics (Graham,Knuth,Patashnik) and I've been reading it for the past few weeks. I'm at the chapter about Sums (Chapter 2), specificaly, the lesson ...
1
vote
1answer
159 views

Homework problem on identifying a sequence

I had this problem in my discrete math/modular arithmatic course where I had to find the first 10 terms of a series F(r), starting from F(3). The given information is: F(3)=1 F(4)=13 F(10) % ...
2
votes
1answer
144 views

Is there any binary relation operator that has these properties in any objects?

Consider binary relation operators d b q p (with a direct correspondence by generalization of: < > ≮ ≯ these are a ...
1
vote
3answers
374 views

Can a graph with 7 vertices and 17 edges have an isolated vertex?

The question is: Show or disprove that a graph with 7 vertices and 17 edges can have an isolated vertex. I know what is an isolated vertex, but don't know how to connect it with the concrete ...
1
vote
0answers
61 views

Characteristic polynomial of the tree

How can one show that a coefficient of $\lambda^{n-2k}$ in characteristic polynomial of the tree is a number of matchings of size k in this tree. $n$ is a number of vertexes in the tree.
0
votes
1answer
119 views

“Simmetric” connected k-regular bipartite graph

Let $G$ be a k-regular bipartite graph with $k > 0$. Then it is known that the two sets which partition the vertex set of $G$ have the same cardinality. However I am interested in connected ...
1
vote
1answer
41 views

A Catalan-like counting of walks of length $n$ on $\mathbb{Z}$

I would like to count the number of walks of length $n$ on $\mathbb{Z}$ starting at $0$, where in each step you move either one left or one right, such that you never land on a negative integer (i.e. ...
0
votes
1answer
153 views

arrange numbers into 3 groups (by sum) in an ordered list

I am looking for a way to group numbers into 3 groups, which each group has a sum as close to others as possible. And the order of original list is preserved. For example , here is a list: ...
4
votes
2answers
205 views

Telephone Number Checksum Problem

I am having difficulty solving this problem. Could someone please help me? Thanks "The telephone numbers in town run from 00000 to 99999; a common error in dialling on a standard keypad is to punch ...
2
votes
1answer
70 views

Equivalence classes - on $\mathbb{N}^2$

Let $R$ be the relation on $\mathbb{N}^2$ defined by $(a,b)R(c,d)$ if $2a + 3b = 2c + 3d$ Write $4$ elements in the equivalence class of $(1,2)$ So I think I need to find all the pairs $(a,b)$ with ...
0
votes
1answer
365 views

Can there be a repeated edge in a path?

I was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph "A walk in a graph is an alternating sequence of vertices and edges ...
2
votes
2answers
850 views

How to apply De Morgan's law?

If for De Morgan's Laws $$( xy'+yz')' = (x'+y)(y'+z)$$ Then what if I add more terms to the expression ... $$(ab'+ac+a'c')' = (a'+b)(a'+c')(a+c)?$$
3
votes
2answers
104 views

Concrete Mathematics Iversonian Set Relation Clarification

Sorry for asking a very dumb question, but in Concrete Mathematics(Graham,Knuth,Patashnik), chapter 2 section 4, Knuth talks about this formula called "Rocky Road". This is the formula to use when ...
2
votes
1answer
311 views

“Rules of inference” when the last premise is a conditional?

Another very basic Discrete Mathematics homework problem. I don't want the answer as much as I want to understand the question: Problem 7 For each of the following sets of premises, ...
2
votes
2answers
115 views

Prove that $n! < n^n $ where n >1 and is an integer , why do some people say my solution is wrong?

Prove that $n! < n^n $ where n >1 and is an integer. Lets skip the base case cause its trivial. Assume that: $$ k! < k^k = $$ Inductive step: $$(k+1)! < (k+1)^{k+1} =$$ $$(k)!(k+1) < ...
1
vote
0answers
35 views

Weights for degree ordering

Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k\geq 3$. Consider the set $M$ of all monomials of the form $x_1^{i_1}.x_2^{i_2}.x_3^{i_3}$ where each $i_j\in \mathbb{N}$ with $i_j\geq 1$ and ...
2
votes
1answer
29 views

computing recursive functions

I have a function $\alpha : \mathbb{N}\times\mathbb{N} \rightarrow\mathbb{N}$, defined recursively, as below: $\forall n \in\mathbb{N}, \alpha(n,10) := \begin{cases} \alpha(n-1-9, 10) + 9 ...
1
vote
2answers
710 views

Basic discrete math question regarding translation of logic ↔ English

I just started Discrete Mathematics, and am having a little bit of trouble in understanding the conversions of English ↔ logic. $p$: "you get an A on the final exam." $q$: "you do every ...
0
votes
1answer
81 views

Why is this summation formula wrong?

This is the alternate form of the summation formula: $$ \sum^{n}_{k=0} a(c)^k = \frac{ac^{n+1} - a}{c - 1} $$ so why is this wrong? $$ \sum^{n}_{k=0} (-\frac{1}{2})^k = \frac{(-\frac{1}{2})^{n+1} - ...
2
votes
1answer
177 views

Concrete Mathematics Solving Double Summation Clarification

I think this question may be viewed as too simplistic, or even dumb with respect to the other types of questions asked on this site. In chapter 2 section 4 (multiple sums) of Concrete ...
1
vote
2answers
232 views

Study regimen for discrete mathematics? - Lack high-school maths…

I have just gotten into college, and will be studying mathematics from next semester. (this course) Unfortunately I did not study mathematics for the last 2-3 years of high-school mathematics. What ...
0
votes
1answer
98 views

Optimal strategy for covering all possible subsets

I was playing a game, and I started wondering about this: In the game Little Inferno, there are lots of items, and burning a particular subset of them gives you a combo. The "Deadly Vices" combo ...