The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

1
vote
2answers
45 views

Simple expression for $\sum_{k=1}^{n-1}\:\frac{1}{k\left(k+1\right)}$

I know that $\:\:\frac{1}{k\left(k+1\right)}\:\:\:\:=\:\frac{1}{k}\:-\:\frac{1}{k+1}\:$ And that $\sum_{k=1}^{n-1}\:k$ $= \frac{n(n-1)}{2}$ But I'm not completely sure how to turn $\sum_{k=1}^{n-1}...
1
vote
1answer
53 views

If $m | (8n +7)$, $m | (6n + 5)$, prove that $m = ± 1$

If $m | (8n + 7)$, $m | (6n + 5)$,prove that $m = ± 1$ -We have just starting going over the "divides" notation, and I am aware of a few properties and theorems from my notes. I am; although, a bit ...
1
vote
2answers
63 views

Proof with Combinatorial Argument $\sum_{i = 1}^{n} (i-1) = nC2$

I am trying to prove below equation with combinatorial argument but I have no idea how this works. $$\sum_{i = 1}^{n} (i-1) = nC2$$ Can anyone give me a clue?
1
vote
1answer
38 views

Sum of Reciprocals

I wonder if someone help me with this: I have $\pi_1+\pi_2+ \pi_3 +\pi_4=A$ and $\pi_1\pi_2\pi_3\pi_4=B$ where $\pi_i \;\forall i=1,2,3,4$ are unknown but $A,B$ are known numbers. Can I find for ...
1
vote
2answers
35 views

Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent.

I am new in Discrete Math so that I am still not familiar with Logical Equivalent rules. 1) Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent. My Try: ¬p ∨ (r →¬q) $\equiv$ ¬p ∨ (¬r∨ q) [...
1
vote
2answers
43 views

Counting problem (students assigned to a tutor)

Four new students have to be assigned to a tutor. There are seven possible tutors, and none of them will accept more than one new student. In how many ways can the assignment be carried out? The ...
1
vote
2answers
47 views

Guide to solving Harary's exercises

Most of Harary's harder exercises are research problems (although solved), that need almost always a single key idea as a breakthrough. Often it so happens that even after thinking for a long time no ...
1
vote
2answers
35 views

Why a truncated table for logic implication $(p\wedge q) \implies p$ verification?

The book Discrete Mathematics by Kenneth A. Ross says: "Let's verify the logic implication $(p\wedge q) \implies p$. For that, we need to consider only just the case when $p\wedge q$ is true; i.e., ...
1
vote
1answer
51 views

How can I find the size of this set?

I'm sorry in advance for my bad english. I got this question for homework and just can't solve it: There are 2 sets, $A$ and $B$ which are contained in $\mathbb{N}$ (the set of all natural numbers)...
1
vote
3answers
76 views

Is 'Some of x are true' a negation of 'All of x are true'?

I don't think this necessarily means there exists a false x, just that at least some x are true. Is my logic correct here in ...
1
vote
2answers
75 views

Proving Wiener's attack on RSA: help understanding what is meant by a “classic approximation relation”?

I am researching Wiener's attack on the RSA cryptosystem. The theorem, found here beginning on page 4, is as follows: Let $N=pq$ with $q < p < 2q$. Let $d < \frac{1}{3}N^\frac{1}{4}$. Given ...
1
vote
5answers
41 views

Proving a relation on Z×(Z-{0}) is an equivalence relation

Question:Let $X=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$. Define a relation $\sim$ on $X$ by declaring that $(a, b)\sim(c, d)$ if and only if $ad = bc$ Prove that the relation $\sim$ is an ...
1
vote
2answers
68 views

Leaping frog algorithm

I need your help with a riddle, I need to find the best algorithm to catch a frog, The frog is on the Natural numbers, it begins at point L, each time it goes K Leaps right (means if it was at point X,...
1
vote
1answer
57 views

What is the probability that you have a Straight Flush if you have a Flush?

I dont have poker game knowledge. Any suggestion for this? The probability of drawing a flush is .001980439. The probability of drawing a straight flush is 0.00001544.
1
vote
1answer
50 views

Generating function of the sequence

Find the generating function of the sequence with $$a_n = \frac{(6^n+1)^2}{2^n}.$$ First of all I writed it like that $\displaystyle G(x) =\sum\limits_{n=0}^\infty\left(\frac{(6^n+1)^2}{2^n}\...
1
vote
2answers
40 views

Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

I have this math question that I'm kind of stuck on. Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$ I have to use mathematical ...
1
vote
1answer
31 views

What is the probability of drawing a hearts when the first card you draw was spade? Please check the description

Intuitively we know that when the first card drawn was Spade, it left $13$ hearts and $51$ cards so the probability is $13/51$. I was trying to solve it by the formula of conditional probability P(B|...
1
vote
3answers
49 views

Combinatorics - arranging people in a circle with a condition

Adam has 12 children In how many ways we can arrange his children around a circle table if Josh cannot sit next to Mark? My solution to this is: The total number of permutations for a circle is: $(n-...
1
vote
3answers
65 views

Why must an inverse function be bijective?

Explain why $f^{-1}$ is a function if and only if $f$ is a bijective function. My attempt: $f^{1}$ is the inverse relation from B to A $\equiv$ function from B to A By definition of a function ...
1
vote
1answer
37 views

If a phone number is allowed to start with any digit, including 0, how many 6- digit phone numbers have distinct digits?

If a phone number is allowed to start with any digit, including 0, how many 6- digit phone numbers have distinct digits? have distinct digits, and don’t start with 0.
1
vote
2answers
37 views

Constructing a recurrence relation regarding binary sequences

For each positive integer $n$, let $a_n$ be the number of binary sequences of length $n$ which do not contain the subsequence $011$. Construct a recurrence relation for $a_n$. My attempt: Initial ...
1
vote
2answers
40 views

Divisibility of an expression

Need some guidance How to prove that $9\cdot n^9+7\cdot n^7+3\cdot n^3+n$ is divisible by $10$. I've tried transforming the expression by adding $n^9$ and $-n^9$ in order to make a multiple of 10 ...
1
vote
2answers
49 views

What is the general solution to 12x = 9 (mod n)?

I know how to solve specific cases but can't find a way to express the solutions for a general n.
1
vote
1answer
42 views

System of congruence relations

Solve the system of congruence relations: $2x+3y\equiv 1\pmod {11}$ $x+4y\equiv 4\pmod {11}$ Could someone give a hint how to solve this system. I know that Chinese remainder theorem can't be used ...
1
vote
1answer
37 views

Determine the language accepted by this DFA (in English)

Having trouble finding the pattern for the language of this DFA: I can see that anything in the language must start with an a, but after that I cant see how you would generalise all the possible ...
1
vote
2answers
21 views

Probability of 2 n-permutations meeting in k places.

I have been thinking about think problem, however, I still do not really know how to tackle it. We have two permutations of $n$ elements. What is the probability that these two permutations meet in ...
1
vote
2answers
90 views

if $a ≡ b\pmod {2n}$ then prove $a^2 ≡ b^2 \pmod {4n}$

Let $n$ be positive number, if $a \equiv b \pmod{2n}$, prove that $a^2 \equiv b^2 \pmod{4n}$. By the congruence in hypothesis, we have $a-b = 2nk$ where $k$ is an integer. Then $a = b+2nk$ and $a^...
1
vote
1answer
132 views

Union of two graphs

Let $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 ∩ G_2 = (V, E_1 ∩ E_2)$ is not a connected graph, then the graph $G_1 U ...
1
vote
2answers
52 views

Discrete math - confusion in onto functions

The question that I'm trying to solve is: At the CH Company, Joan, has a secretary Teresa, and three other administrative assistants. If seven accounts must be processed, in how many ways can ...
1
vote
1answer
50 views

Induction: Prove that if $p$ is a prime number, then the sum of squares is divisible by $p$

Use the Theorem $$1^2+2^2+....+n^2 = \frac{n(n+1)(2n+1)}{6}$$ to prove that if $p$ is any prime number with $p \geq 5$, then the sum of squares of any $p$ consecutive integers is divisible by $p$. I'...
1
vote
2answers
98 views

Write the following for loop as a double summation

So I'm having trouble with convert a for loop with a nested for loop into a double summation. Mainly I think that I'm at a loss of how exactly to form a double summation. The following for loop is ...
1
vote
2answers
33 views

Multiple modulis, trying to find 1 number

I won't quote here the full question, because it's irrelevant. ${x \in \mathbb{N}}$ ${x \le 250}$ ${x \mod 8 = 1}$ ${x \mod 7 = 2}$ ${x \mod 5 = 3}$ So my idea was to write down ever number that ...
1
vote
3answers
204 views

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$.

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$ using the Pigeonhole principle. I am supposed to identify the pigeons and the pigeonholes. ...
1
vote
1answer
30 views

Let $(a_n)_{n\geq 1}$ be a sequence of integers defined by $a_1=1, a_2=2$, and for each $n\geq 1$, $a_{n+2} =a_{n+1} +3a_n$.

I am trying to learn how to write out the equations correctly. Sorry in advance. Let $(a_n)_{n\geq 1}$ be a sequence of integers defined by $a_1=1, a_2=2$, and or each $n\geq 1$, $a_{n+2} =a_{n+1} +...
1
vote
4answers
80 views

Prove that $(1 + \sqrt2)^{2n} + (1 - \sqrt{2})^{2n}$ is an even integer.

Prove that $(1+\sqrt2)^{2n} + (1-\sqrt2)^{2n}$ is an even integer. I'm not sure how to prove that it is an even integer. What would I do for the Inductive Step? And for the basic step, can I plug in ...
1
vote
2answers
265 views

Number of squarefree positive integers less than $100$

An integer is called squarefree if it is not divisible by the square of a positive integer greater than $1$. Find the number of squarefree positive integers less than $100$. My attempt: I apply ...
1
vote
1answer
49 views

A binary sequence graph

Define a graph $H(n, 2)$ as follows. Each vertex corresponds to a length $n$ binary sequence and two vertices are adjacent if and only if they differ in exactly two positions. I want to find ...
1
vote
2answers
43 views

Prove using induction that $2^n < \binom{2n}{n} < 4^n$ for $n \geq 2$

Trying to prove that, for $n\geq2$, $2^n < \binom{2n}{n} < 4^n$. Inductive hypothesis: Assume $P(k)$ is true: \begin{align} 2^k < \binom{2k}{k} < 4^n \\\\ \end{align} Show $P(k+1)$ \...
1
vote
1answer
69 views

Show that for every set of 18 integers there will be two that are divisible by 17 [closed]

I understand the pigeonhole principle is needed here and I see the solution in the back of the book, but the explanation is week. If anyone could explain step-by-step that would be awesome!
1
vote
2answers
30 views

Find all non-negative integral solutions $(n_1, n_2, …, n_{14})$ to $\sum^{14}_{i=1} n_i^4 = 1599$.

Find all non-negative integral solutions $(n_1, n_2, ..., n_{14})$ to $\sum^{14}_{i=1} n_i^4=1599$. I have a bit of difficulties to start the problem. Is anyone is able to give me a hint? Please I ...
1
vote
3answers
63 views

Two out of five in a group have the same number of friends…

I recently came across a problem- Prove that in a group of five people,there are two who must have the same number of friends in the group. I assume it must be solved by Pigeon Hole Principle (...
1
vote
2answers
62 views

Proving $1\cdot1! + 2\cdot2! + 3\cdot3! + … + k\cdot k! = (k+1)! - 1$ [duplicate]

How could one prove by induction that: $$\forall{n}\in{N}:1(1!)+2(2!)+3(3!)+...+n(n!)=(n+1)!-1$$ My attempt so far: Base case: Let n = 1, 1(1!) = (2)! - 1 = 1, holds true for LHS = RHS. Inductive ...
1
vote
1answer
55 views

For every partial order ≤ is the relation < transitive?

For every general partial order ≤ is the relation < := ≤ ∩ ≠ transitive I tried working with the definition of the partial order. A partial order is antisymmetric, transitive and reflexive. The ...
1
vote
1answer
75 views

Can a number written using one hundreds 0's, one hundred 1's and one hundred 2's be a perfect square? [duplicate]

Question: Can a number written using one hundreds 0's, one hundred 1's and one hundred 2's be a perfect square? I have no idea where to start.
1
vote
2answers
293 views

Show that f(x)=e^x from set of reals to set of reals is not invertible…

Yes, this is my question... How can you prove this? That $f(x)=e^x$ from the set of reals to the set of reals is not invertible, but if the codomain is restricted to the set of positive real numbers, ...
1
vote
1answer
213 views

Tile a 1 x n walkway with 4 different types of tiles…

Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile a. Set up and explain a recurrence ...
1
vote
2answers
164 views

Prove that there must be two distinct integers in $A$ whose sum is $104$.

Let A be any set of $20$ distinct integers chosen from the arithmetic progression ${1,4,7,...,100}$. Prove that there must be two distinct integers in $A$ whose sum is $104$. Define $A=\{1+3i\}_{...
1
vote
1answer
183 views

How many ways are there to choose 10 coins with at least 3 nickels but no more than 2 quarters?

A piggy bank contains 50 pennies, 40 nickels, 30 dimes, and 20 quarters. (1) How many ways are there to choose 10 coins with at least one of each type? (2) How many ways are there to choose 10 coins ...
1
vote
2answers
34 views

Show that if $T$ is a subset of $S$ having more than $16$ elements then $T$ contains two elements whose distance is at most $2$.

Let $S = \{0000000, 0000001, ... , 1111111 \}$ be the set of all binary sequences of length $7$. The distance of two elements $s_1 ,s_2 \in S$ is the number of places in which $s_1$ and $s_2$ differ....
1
vote
2answers
49 views

Find $a_i, b_i$ such that they are all distinct

Very tough, I spent at least an hour, not solving this! From the set of integers $ \{1,2,3,\ldots,2009\}$, choose $ k$ pairs $ \{a_i,b_i\}$ with $ a_i<b_i$ so that no two pairs have a common ...