Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
1
vote
2answers
30 views
Aquaintance problem in discrete math. induction proof.
I'm supposed to prove this by induction. I already proved it by contradiction, but I am lost on how to set it up for induction.
Prove that if at least two people are at a party, at least two of ...
1
vote
1answer
30 views
Handshake problem. discrete math.
at a party, 25 guests mingle and shake hands. prove that at least one guest must have shaken hands with an even number of guests.
2
votes
1answer
25 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
12 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
40 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 ...
28
votes
22answers
916 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
42 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
votes
3answers
39 views
How do I prove that if $\gcd(a, b) = d$ and $\gcd(b, c) = 1$, then $\gcd(a, c) = 1$ [closed]
If $\gcd(a, b) = d$ and $\gcd(b, c) = 1$ prove that $\gcd(a, c) = 1$
I would assume that since $\gcd (b,c) = 1$ then: $b\nmid c$ and $c\nmid b$
Not sure how that helps..
Any idea's?
1
vote
4answers
49 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
301 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
48 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
22 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
41 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
64 views
discrete math counting problem
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 ...
1
vote
0answers
38 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
57 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
39 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
27 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
60 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
47 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
23 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
28 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 ...
3
votes
2answers
42 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
48 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
34 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
23 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
62 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
55 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
30 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
50 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 ...
1
vote
1answer
70 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
143 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) % ...
1
vote
3answers
58 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
41 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
45 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 ...
-3
votes
0answers
36 views
Determine the equivalence classes for each of these equivalence relations. [closed]
Define three equivalence relations on the set of students in your discrete mathematics class different from the relations discussed in text. Determine the equivalence classes for each of these ...
1
vote
1answer
27 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
36 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
49 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
62 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
37 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
65 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
50 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
99 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) < ...
0
votes
0answers
31 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
19 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
55 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
69 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} - ...
0
votes
1answer
34 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 ...
2
votes
1answer
37 views
Help with brute force method of producing bifurcation diagrams of discrete-time systems
I have a homework question concerning a brute force method of creating bifurcation diagrams. This seems really abstract for me and would like a clearer description of how the method works. Can someone ...
