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

0
votes
0answers
34 views

Asymptotical stability of a discrete dynamical system

There is a linear time invariant discrete system, \begin{align} x_{k+1}&=\tilde{A}x_k, \end{align} where $\tilde{A}$ is a block matrix represented by \begin{align} \tilde{A}= \left(\begin{array}...
-1
votes
1answer
73 views

What is the inverse function of gcd? [closed]

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
0
votes
1answer
175 views

Find the number of flags of different types using induction

A flagpole is $n$ feet tall. On this pole we display flags of the following types: red flags that are $1$ foot tall, blue flags that are $2$ feet tall, and green flags that are $2$ feet ...
0
votes
0answers
28 views

Repertoire method in solving recurrence [duplicate]

I don't know, how should I start solving this: $$a_1 = 2 \\ a_n = 2a_{n-1} +7$$ using the repertoire method. Could anyone give me an algorithm or explain, how to use this method in this case?
0
votes
3answers
43 views

Proving $a=b \bmod 19$ is an equivalence relation

My question is: $a \equiv b \bmod {19} \iff aRb$ (prove that $R$ is an equivalence relation) Before that, I already know that equivalence relation is when $R$ is reflexive, symmetric and ...
0
votes
1answer
30 views

defining a sequence of numbers L n≥1, and prove something about it

So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek ...
4
votes
6answers
224 views

Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

Here is the proof: Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. When working these problems, I do try to set them up logically. My ...
2
votes
3answers
88 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
3
votes
2answers
72 views

number of triangles determined by a rectangular grid

Suppose we are given an $m\times n$ rectangular grid of lattice points, such as $S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine the number of (...
0
votes
1answer
54 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...
0
votes
0answers
69 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
1answer
58 views

consider a graph of a gameboard

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the ...
0
votes
1answer
48 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and $(5)[3]...
0
votes
1answer
16 views

About cycles and the values in the range of a permutation function

Let $f = \{(x_1 y_1), (x_2 y_2), \ldots, (x_n y_n)\}$ be a permutation. A cycle of $f$ is given by $g = (1, f(1), f^2(1), f^3(1) \ldots)$. When counting permutations, we usually drop $1$ and count ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
0answers
24 views

Multigraphic Degree Sequences

Given a degree sequence $\{d_1,d_2,\ldots,d_n\}$, can I determine in polynomial time in $n$ whether this sequence is multigraphic AND can be realized by a connected multigraph? Looking at this paper,...
0
votes
0answers
19 views

Integer problem to minimize cuttings

A company has to make 4 items in the given quantities. item1 =4 item 2=2 item3=1 item 4=1 Te surfaces has to be covered in plywood.The company has got 3 ...
0
votes
0answers
34 views

Let $(12)$ and $(23)$ be cycles. Then is $(12)(23)$ a permutation?

The reason I ask this is because sometimes we talk about non-disjoint cycles, for example: $(ab)(bc) \neq (bc)(ab)$. Do we consider $(ab)(bc)$ a permutation where $f(b) = a$ and $f(b) = c$?
-4
votes
1answer
67 views

Prove that there doesn't exist any integer $x \ge 3$ such that $x^2-1$ is prime. [closed]

Prove that there doesn't exist integer $x \ge 3$ such that $x^2-1$ is prime.
1
vote
1answer
30 views

Countability of the set of weighted graphs

Could you help me find the solution for this problem that consists in finding out wether the set of all weighted and finite graph is countable of not? As a reminder, a weighter graph can be seen as a ...
1
vote
1answer
42 views

Graphically representing relations of ordered pairs

I am having problems trying to picture what this relation of ordered pairs 'looks' like: Let R be the relation on the set of ordered pairs of positive integers such that ((a, b),(c, d)) ∈ R if and ...
1
vote
1answer
30 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
0
votes
3answers
54 views

Proving ${\sum}^n _{i=1}i = \frac {n(n+1)}{2}$ by induction

I am having problems understanding how to 'prove' a summation formula. I have the equation: $ {\sum}^n _{i=1}i = \frac {n(n+1)}{2} $ Basis Step when: $ n=1 $ $ {\sum}^1 _{i=1}i = \frac {1(1+1)}{...
2
votes
1answer
53 views

Property of maximum matching

Let $G=(V,E)$ be a graph with no perfect matching. Then there exists a vertex v such that every incident edge is part of a maximum matching. I'm not sure how to prove this. How can every edge that ...
0
votes
1answer
37 views

Projection of a discrete subgroup of $R^n$ [duplicate]

Let $A$ be a discrete subgroup of $\Bbb R^n$ and let $V$ be a $m<n$ dimensional $\Bbb R$-subspace of $\Bbb R^n$. Is the projection of $A$ onto $V$ a discrete subgroup? I am most interested in the ...
2
votes
2answers
35 views

Shortcut for composing cycles

Let $\pi = (15)(14)(13)(12).$ To compose the cycles of $\pi$, I rewrite $(15)(14)(13)(12)$ as $[(15)(2)(3)(4)][(14)(2)(3)(5)][(13)(2)(4)(5)][(12)(3)(4)(5)]$ which is tedious. Is there any way to ...
0
votes
2answers
46 views

Verifying the reasoning is true for the following deductive arguent

Identify the premises and conclusions of the following deductive arguments and analyze their logical forms. Do you think the reasoning is valid? Either John or Bill is telling the truth. Either Sam ...
2
votes
1answer
68 views

Smallest integer

I encountered an intriguing problem and I think I have a solution, but I want to run it by some of the smarter people around here: Find the smallest integer $n, n>1$ such that $C(n)=n, C(n)$ is ...
0
votes
1answer
67 views

Finding a twin prime in binary expansion

Numbers from 1 to 63 are placed on 6 cards according to the following 6 rules: The 1st digit in the binary expansion of each number on card 1 is a one. The 2nd digit in the binary expansion of each ...
0
votes
1answer
59 views

3 men and a cold night [duplicate]

$3$ guys, each with $\$10$ a piece, go to a hotel hoping to get a room to stay in for the night. A room costs $\$60$. The men go in, and ask to rent a room, only having $\$30$ between them. The mater ...
2
votes
0answers
57 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence $b_{m}=...
1
vote
1answer
48 views

General methods of solving non-linear recurrences

Let's consider a sequence $$ \{a_{n} \} _{n=0}^{\infty}, a_{0}=1, a_{n+1}=\frac{a_{n}}{1+na_{n}}$$. Taking $$b_{n}=\frac{1}{a_{n}},$$ we bring the exact reccurence to the following one: $$b_{0}=1, ...
0
votes
2answers
62 views

Induction question regarding Universe

I was given a question that looks like this. Prove that for each $2 \le n\in \mathbb N$, if $X_1,\ldots,X_n$ are subsets of some universe $U$, then the following is true: $$(X_1 \cup\cdots\cup X_n)^...
0
votes
1answer
54 views

Discrete mathematics, equivalence relations, functions.

I'd like some insight on how to 'solve' this problem (more towards understanding what the problem is asking) Suppose that $A$ is a nonempty set and $\mathcal{R}$ is an equivalence relation on $A$...
0
votes
0answers
20 views

Combinatorial nature of discrete-valued variables

Can I ask what this statement means? An example would be preferred. Due to the combinatorial nature of discrete-valued variables, rare values are more acutely felt than in numeric variables.
1
vote
3answers
91 views

proof by induction $2^n \leq 2^{n+1}-2^{n−1}-1$

My question is prove by induction for all $n\in\mathbb{N}$, $2^n \leq 2 ^{n+1}-2^{n−1}-1$ My proof $1+2+3+4+....+2^n \leq 2^{n+1}-2^{n−1}-1$ Assume $n=1$,$1 ≤ 2$ Induction step Assume statement ...
1
vote
1answer
108 views

Minimization of a combinatorial function

The following gamma function depends on the overall sum of $x_n,x_j,x_k$ $$\gamma(X)=\sum_{x_n+x_j+x_k=X}\left [ \left ( \prod_{i=1}^{s}(x_{ni}-1)!C_i^{x_{ni}} \right )\times \binom{x_j}{x_{j1},x_{...
0
votes
0answers
41 views

Exponential cryptosystem

The cryptosystem works as follows: The plaintext message is first replaced by ciphers (a=00, b=01, etc.) and then encrypted in blocks of four digits. So if the message is "hi", the plaintext number ...
3
votes
3answers
1k views

a natural number that is both a perfect square and a perfect cube is a perfect sixth power?

I really can't get a grasp on how to prove this, because if $x$ = $\sqrt[6] n$ for some $n$, then $x^2$ = $a$ and $x^3$ = $b$, with $a$ and $b$ being different natural numbers right? Any help?
0
votes
3answers
104 views

Compute equivalence classes of equivalence relation

I have already proven that the relation $R=\{(x,y) \in \mathbb Z \times \mathbb Z \mid x+y\text{ is even}\}$ is an equivalence relation by showing reflexive, symmetric, and transitive properties of ...
2
votes
2answers
60 views

Strong Induction to prove $T(n)$ is $O(n)$ for $T(n) = T(\lfloor n/3 \rfloor) + T(\lfloor n/5 \rfloor) + T(\lfloor n/7 \rfloor) + n$

I have some questions about Strong Induction where the inductive procedure isn't entirely clear to me. I will use a specific example to demonstrate and present my attempt at a proof with questions ...
2
votes
2answers
122 views

Prove that rational numbers $a,b$ are integers if $a+b$ and $ab$ are integers

I have been trying to prove this via divisibility, assuming that $a=\frac{n}{m}$ and $b=\frac{r}{q}$ for some $n,m,r,q$ in Ints($m$,$q$ not $0$), but I'm completely stuck here. Any help?
4
votes
1answer
60 views

Arranging the letters of INCONVENIENCE so that no C is adjacent to an N

As the title indicates, I would like to find the number of ways to arrange the letters of INCONVENIENCE so that no C is adjacent to an N. This is a problem I just made up, and I am interested in ...
1
vote
2answers
135 views

Find k integers that can make up all integers below N.

For given $N$, what is the smallest $k$ so that we can find $k$ natural numbers satisfiying some of these $k$ numbers can add up to any $i$ for $1\leq i\leq N$. Moreover, how to find all possible $k$ ...
0
votes
0answers
37 views

recursive definitions using sequences

lets say I have 2 sequences $$a_0, a_1,\ldots, a_n,\ldots$$ and $$b_0, b_1,\ldots, b_n,\ldots$$ where $$a_k \text{ and } b_k$$ are defined as: $$ a_n = \sum_{k=0}^n {n+k \choose 2k}, \quad \quad n\...
-2
votes
2answers
140 views

general formula using informal inductive reasoning

if I have 4 equations.. $$ 1=1$$ $$2+3+4=1+8$$ $$5+6+7+8+9=8+27$$ $$10+11+12+13+14+15+16=27+64$$ how do I find the general formula (that is suggested by the equations) using informal inductive ...
-1
votes
4answers
109 views

For all integers $x$ and $y$, if $ x^3 + x = y^3 + y$ then $x = y$. [duplicate]

For all integers $x$ and $y$, if $x^3 + x = y^3 + y$ then $x = y$. This is what I have done so far: Proof: Suppose $x$ and $y$ are arbitrary integers. We know that $x^3 + x = y^3 + y$, we want to ...
2
votes
4answers
268 views

Proof - for all integers $y$, there is integer $x$ so that $x^3 + x = y$

For all integers $y$, there is an integer $x$ so that $$x^3 + x = y.$$ This is what I have done so far: Proof: Suppose $y$ is some integer. We want to prove that $$x^3 + x = y$$ for some integer $x$....
-6
votes
1answer
52 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = -1 ...
2
votes
0answers
94 views

Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...