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

learn more… | top users | synonyms

1
vote
1answer
41 views

Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$

Question: Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$ (Hint: Look for a particular solution of the form $qn2^n + p_1n + p_2$, where $q, p_1, p_2$ are ...
1
vote
0answers
27 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
-1
votes
0answers
42 views

proof of a theorem in a paper

I was reading a paper named decomposition of kronecker product of cycles and path into long cycles and paths. In one theorem I have a doubt. I am not getting how the proof of Lemma 1.3 is done. I am ...
1
vote
1answer
18 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
1
vote
0answers
42 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
3
votes
1answer
20 views

Partitioning a totally ordered set into three subsets according to the order

Consider a set $S$, and a total order $R$ over that set. Part (a) Given some element $e \in S$, explain why it is possible to partition $S$ into the following three sets: $$S_1 = \{ x \in S ...
1
vote
3answers
63 views

Recurrence solution of simple recurrence

Please help me to find the solution of the recurrence in terms of n(implies $(f(n))$ and also the summation of the recurrence up to infinity ($sum = \sum_{n=0}^\infty f(n)$) . ...
2
votes
1answer
26 views

Relations examples (reflexivity, symmetry, transitivity)

I've found the two textbooks I'm using to to be particularly unhelpful in explaining these concepts, especially as they relate to English examples (non-existent). The first few following questions ...
1
vote
1answer
29 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
0
votes
2answers
24 views

Which is kernel similar gaussian kernel?

I must find a kernel that statisfies as follows: In the my reference paper, the author suggest gaussian kernel that is The purpose of that kernel is that it will take a weight for each points ...
1
vote
0answers
16 views

Why is this directed graph strongly connected?

From what I can see, there is no vertex path that goes to 1 so why is it strongly connected? Shouldnt every vertex be reachable from every other vertex? In this picture the 1 is not reachable.
0
votes
1answer
18 views

Let x, y be integers. Show that if x = y (mod n), then x + mZ = y+mZ,and conversely, if x+mZ=y+mZ then x = y (mod n)?

Let $x, y$ be integers. Show that if $x = y\mod n$, then $x + nZ = y+nZ,$ and conversely, if $x+nZ=y+nZ$ then $x = y\mod n$? I have no a clue on how to prove this! Please help.
-1
votes
0answers
43 views

Discrete Mathematics Proof about coefficients in a Function [on hold]

I need to prove these using any method. I know that it deals with the distribution of the coefficients of a function. I just don't exactly know about how to go about proving this. Let the function ...
0
votes
1answer
43 views

Properties of a relation on matrices: $(m_1,m_2)\in R$ iff $m_1\cdot m_2$ is defined

Let $M$ be a set of matrices of integers. Let $R$ be the relation on $M$ defined as follows: For any two $m_1, m_2 \in M, (m_1, m_2) \in R$ iff the matrix multiplication $m_1 \cdot m_2$ is defined. ...
2
votes
2answers
40 views

Find the recurrence relation for the number of bit strings that contain the string $01$.

Question:Find the recurrence relation for the number of bit strings that contain the string $01$. Attempt: Since $01$ can appear in a lot of places, I focused on instances without $01$ first. Bit ...
0
votes
0answers
61 views

Verify/prove theorem Diophantine/GCD

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
2
votes
2answers
44 views

Find the $4$ sq. roots of $100$ in $ U_{209}$. Identify which square root of $100$ is square.

Find the $4$ sq. roots of $100$ in $U_{209}$. Identify which square root of $100$ is square. (Not the $4^{th}$ root, but the $4$ square roots). I honestly don't even know what this question is ...
0
votes
2answers
56 views

Explanation of the formula $f^{-1}(Y)=\{x \in A |f(x) \in Y\}$ for the preimage of a set

So I found a Definition in the book that goes like this to find the pre-image of a set: $$f^{-1}(Y)=\{x \in A |f(x) \in Y\}$$ Example of the theorem being used: Let $A = \{1,2,3,4,5,6\}$ and ...
0
votes
0answers
22 views

Proof of series expansion of $f(k) = {r - sk \choose n}$ in Concrete Mathematics book by D. Knuth, et. al.

Please help me prove this equation in page 190 of Concrete Mathematics 2nd Ed. book by D. Knuth: $f(k) = {r - sk \choose n} = ...
0
votes
2answers
82 views

Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
4
votes
1answer
62 views

Expressing a Recursion in terms of factorials

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = \Gamma(n+1)$$ ...
1
vote
2answers
66 views

Matrix exponential of a skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. Question 1) How do I compute ...
0
votes
1answer
28 views

Diagonalization of Skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. and we have the relation $C=UDU^{-1} ...
-1
votes
3answers
40 views

Exactly why coefficient of $x^ky^{n-k}$ is $C(k,n)$ [duplicate]

in combination when we have a binomial lattices like $(x+y)^n$ the coefficient of $x^ky^{n-k}$ is equal with $C(k,n)$ ... for example we have $(x+y)^4$ so we have this $4$ factor ...
0
votes
0answers
21 views

Stirling number of the second kind and its extension

I have a question regarding Strling's number. For starters we all know that the number of ways in which it is possible to distribute the m distinct objects in to n identical containers with no ...
0
votes
2answers
53 views

Combinatorial Proof to $\sum_{k=0}^n (-1)^k {{n}\choose{k}} = 0$

Question: Combinatorial Proof to $$\sum_{k=0}^n (-1)^k {{n}\choose{k}} = 0$$ I know that by binomial theorem we can derive this, $$0 = ((-1)+1)^n = \sum_{k=0}^n {n\choose k}(-1)^k1^{n-k} = ...
2
votes
2answers
48 views

What are $10^k \pmod 3$ and $n = \overline{a_ka_{k -1} \ldots a_1a_0}$?

I feel like I should know these concepts, but I don't.
1
vote
0answers
9 views

elementary proof for discrete Kantorovich-Rubinstein theorem?

For the Kantorovich-Rubinstein theorem, please see the wikipedia page http://en.wikipedia.org/wiki/Wasserstein_metric (which does not contain a reference for the proof). I am only interested in the ...
4
votes
3answers
52 views

When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$?

Question: When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$? Attempt: $$1XX\\ X1X\\ XX1$$ The count of $1$ for the types above are, $${{3}\choose{1}}*9*9$$ ...
0
votes
1answer
32 views

Question about proving division

Suppose $m = a_k + a_{k -1} + \ldots + a_1 + a_0$. Does $3$ divide $m$? If so, how do we prove that? We know that $3|m \to 3j = a_k + a_{k -1} + \ldots + a_1 + a_0$ for some $j \in \mathbb Z$. ...
0
votes
2answers
36 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
-1
votes
0answers
42 views

set mathematics [duplicate]

Out of 120 customers that visited a supermarket in a day. 62 bought clothing materials, 51 bought provisions and 48 bought kitchen utensils. 15 customers bought both clothing materials and provisions, ...
0
votes
1answer
63 views

Combination Problem with Sofa [on hold]

Suppose we have 5 sofa on room A. in this room, 4 students seated on these sofa. These Strudents go to another room for eating dinner, and after that come back to room A. how many way the students can ...
3
votes
4answers
76 views

Book/Article recommendation

I am a first year Math major in the university, this summer I want to self study and go over some specific subjects. Firstly, can someone can give a suggestion for a detailed book/article about the ...
1
vote
2answers
74 views

Must the centralizer of a non-identity element of a group be abelian?

Q1: Must the centralizer of a non-identity element of a group be abelian? I challenge everyone by asking further about this question one step further. The definition of centralizer is: Let a be ...
1
vote
1answer
25 views

GCD proof - one way solved

Let a,b be positive integers. Prove there exist positive integers $c$, $d$ such that $cd = a$ and $\gcd(c,d) = b$ if and only if $b^2\mid a$. Proof exists $cd=a$ and $\gcd(c,d) = b \Rightarrow ...
0
votes
2answers
25 views

Ways to award first and second place to two persons out of nine

Question: In how many ways can the first and second place be awarded to two persons from among 9 people. ...
7
votes
4answers
172 views

Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question:Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = ...
1
vote
2answers
73 views

Retrieve the initial cubic Bézier curve subdivided in two Bézier curves

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, ...
1
vote
1answer
45 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
0
votes
2answers
69 views

how to find taxicab numbers but for squares?

Natural numbers that can be written as the sum of squares in two or more ways. The first ten numbers are 50, 65, 85, 125, 130, 145, 170, 185, 200, 205. $$ n = a^2 + b^2 = c^2 + d^2\\ a^2 − c^2 = d^2 ...
1
vote
2answers
50 views

If $a_i>o$ then $(a_1a_2\cdots a_{2^n})^{1/2^n}\leq \frac{a_1+a_2+\cdots+a_{2^n}}{2^n}$

I need help to prove this inequality, I have no idea how to proceed with the inductive step: $$a_1,a_2,\ldots,a_{2^n}>0 \Longrightarrow(a_1a_2\cdots a_{2^n})^{1/2^n}\leq ...
0
votes
0answers
18 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
0
votes
1answer
27 views

Combination with repition, Representation techniques.

Consider the following Question:A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernick bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are ...
1
vote
2answers
26 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
2
votes
0answers
87 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
1
vote
3answers
67 views

Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
1
vote
1answer
31 views

Can someone explain the logic behind this step in a induction problem

There is a question in the book that I don't quite understand. Question Show that $n^2$ is smaller than $2^n$ whenever $n\ge5$. At the $k+1$ step it gets very whacked and confusing. $k+1$ ...
1
vote
1answer
36 views

Prove by Structural induction, circular permutations

Prove by Structural Induction: For a circular permutation of $n$ elements, the number of permutations is $(n-1)!$ How is this done?
0
votes
2answers
39 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...