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

2
votes
1answer
32 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
31 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
50 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
51 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 ...
1
vote
1answer
30 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, ...
-2
votes
4answers
89 views

For each natural number $n$, let $A_n = \{nx \mid x\in \Bbb Z\}$. What is $\bigcap^∞_{i=1} A_i$? [closed]

The universe of discourse is the set of all integers. Let $A_n = \{nx \mid x\in \Bbb Z\}$ for each natural number $n$. What is $\bigcap^∞_{i=1} A_i$?
-2
votes
1answer
70 views

Is the following statement true: $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$? [closed]

Is the following statement true: $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$? Having a hard time proving this statement.
0
votes
2answers
56 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 ...
1
vote
1answer
42 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 ...
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
59 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
100 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 ...
0
votes
0answers
29 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
649 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
37 views

Compute equivalence classes of equivalence relation

I have already proven that relation R={($x,$y) $\in$ $\mathbb Z$ x $\mathbb Z$ | $x+$y is even} is a equivalence relation by showing reflexive, symmetric, and transitive properties of the relation. ...
2
votes
2answers
32 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
101 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
54 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
111 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
36 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 ...
-2
votes
2answers
79 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
88 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
101 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 ...
-5
votes
1answer
46 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 = ...
2
votes
0answers
30 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$ ...
1
vote
2answers
45 views

Simple proof by contradiction

I feel like I'm almost there, but I don't know what to right after this: for all real number $x$, if $x^2-2x\neq-1$, then $x\neq-1$. Let $p(x)$ be $x^2-2x\neq-1$ Let $q(x)$ be $x\neq-1$, My ...
1
vote
1answer
56 views

Counting switching functions

By using 16 bit binary in BCD , how many switching functions can exist ? Now , since this is BCD anything above 1001 is invalid. Considering 16 bits : 1001 1001 1001 1001 Above is number of possible ...
0
votes
1answer
52 views

Constructive Induction to derive and prove the formula for a geometric sequence

$\sum_{i=1}^nr^i = a \cdot (b^n) + c$ Base Case: n=1, this holds Inductive Hypothesis: Assume for $n = k$, $k \ge 1$ that $\sum_{i=1}^k r^i = a * (b^k) + c$. Inductive Step: Prove for $n = k+1$ ...
-2
votes
1answer
47 views

model Coin toss probability [closed]

Model the probability of tossing any sequence of 8 heads and tails as equally likely. Take the sample space to be the set of the 256 possible sequences. What is the probability of the event that the ...
2
votes
2answers
72 views

tuple of integers

The integers 1,2,...,30 are invited to a dinner party. They all sit around a round table, in some unknown order. Does there exist an ordering in which there are no three successive (successive means ...
1
vote
1answer
43 views

How to prove generalized DeMorgan's Law? [duplicate]

How to prove generalized DeMorgan's Law that $$\neg(A_1 \land A_2 \land \cdots \land A_n) = \neg A_1 \lor \neg A_2 \lor \cdots \lor \neg A_n.$$ Or in the set theory language, $$\Bigg(\bigcap_{i\in ...
0
votes
2answers
83 views

How does $( 1 - (1- \frac{1}{2^{2^k}}))$ become $(1+ \frac{1}{2^{2^k}})$?

How does $\left( 1 - \left(1- \frac{1}{2^{2^k}}\right)\right)$ become $\left(1+ \frac{1}{2^{2^k}}\right)$? I distributed the former but got negative $-\frac{1}{2^{2^k}}$. So it does not match the ...
1
vote
2answers
46 views

How do I write $2(2^k+1) - 1$ as $(2 \cdot 2^k + 1)$?

How do I write $2(2^k+1) - 1$ as $(2 \cdot 2^k + 1)$? Mathematically, it is equivalent. But I need to the former form into the latter form for step 2 of inductive step for mathematical induction ...
2
votes
1answer
62 views

Is there a general rule for how to pick the base case value for proofs by mathematical induction?

I was looking at how to do mathematical induction. One source said to use $n = 1$ for the basis step. But I have seen other sources choose the value $n = 0$. So the question is as follows: ...
6
votes
4answers
442 views

“If A then B” in Venn (or Euler) Diagrams

How can I represent "If A then B" in a diagram? I thought it would be a simple subset like $A ⊂ B$. However this material says that If $A$ then $B$ $=$ $A^c ∪ B$. Now I am confused.
2
votes
1answer
40 views

Algorithm for generating restricted integer composition of N in k parts from interval [a,b] given the lexicographic number.

Consider the restricted compositions of $6$ in four parts from integers $\{1, 2, 3\}$. ...
2
votes
1answer
29 views

A construction of a Hadamard matrix

Let $H_n$ be a $2^n \times 2^n$ matrix indexed by all subsets of $[n] = \{1,\ldots,n\}$ and let the entry at the intersection of the row and column indexed by the sets $X$ and $Y$ be $$(-1)^{ |X \cap ...
1
vote
1answer
45 views

Number of bit strings

How many bit string of lenght 28 having at least one consecutive 000? without consecutive 000? I'm using ti nspire, can i do it with nCr function. I tried to do it but i did not found a way. ...
1
vote
0answers
30 views

Predicate logic a game where player goes first?

What kind of predicate logic statement describes a game that the person who goes first can always win? Write you answer in terms of successive moves by two players. I am lost here I tried initially ...
2
votes
1answer
53 views

Finding the number of ways to pick ${n}$ marbles from a jar

Problem: А jar contains 8 blue marbles, 6 green marbles, and 4 red marbles. Five marbles are selected at random, all at once. In how many ways can: A.) two red and three blue marbles be obtained? ...
3
votes
7answers
400 views

Grasping the concept of equivalence classes more concretely

I have read about equivalence classes a lot but unable to understand exactly what they are. I know about equivalence relations, but I am having a hard time understanding what equivalence classes are ...
7
votes
2answers
62 views

How do I solve for P in this equation? (involving floor functions) edited

I have the following equation: $$ A=\frac{\left \lfloor (n+1)^{P} \right \rfloor}{\left \lfloor n^{P} \right \rfloor} $$ How to solve for P using A and n? *n is a non negative integer *A and P are ...
2
votes
1answer
59 views

Combinatorics: How many ways are there to distribute zero to thirteen distinct cards to four distinct players?

Other ways to word the question so that it's clear: In a game where players hold a maximum of thirteen cards and a minimum of zero cards, how many possible positions are there? How many possible ...
0
votes
1answer
20 views

Proofs for certain ways of decomposing permutations as products of transpositions

I know $(1 2 3 4 5) = (15)(14)(13)(12)$. But I just discovered $(12345) = (12)(23)(34)(45)$ and $(12345) = (54)(52)(21)(25)(23)(13)$. Also, $(15) = (21)(32)(43)(54)(43)(32)(21)$. Excepting the ...
0
votes
1answer
87 views

A puzzle about choosing one of 9 doors with signs on them

This problem involves logic-based math, I tried making truth tables for this problem but I don't think you can because there are 9 doors! Below is what I came up with but I want to know if there is a ...
3
votes
2answers
46 views

Finding the number of ways of picking three cards

Problem: An urn has 10 red cards numbered 1 through 10 and 8 blue cards numbered 1 through 8. Three cards are randomly drawn, one at a time, without replacement. Find the number of ways to ...
3
votes
2answers
63 views

Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three ...
1
vote
1answer
21 views

Questions about terminology (transpositions)

A cycle with only two elements is called a transposition. For example, the permutation of $\{1, 2, 3, 4\}$ that sends $1$ to $1$, $2$ to $4$, $3$ to $3$ and $4$ to $2$ is a transposition ...
-5
votes
1answer
38 views

Prove $a_n =\frac{ (n^2+n+6)}{2}$ [closed]

Let $a_n = 0$ and for $n>0$ let $a_n = a_{n-1} + n$. Prove $$a_n =\frac{ (n^2+n+6)}{2}$$ The only way I knew how to prove the recurrence relation is: $a_n = a_0+ nt$ but it doesn't work in ...
1
vote
1answer
32 views

Nearly-unit-distance graph (UDG) density

Q1. How dense can a nearly-unit-distance graph be? Let points sit in $\mathbb{R}^2$. A unit-distance graph UDG "connect[s] two points by an edge whenever the distance between the two points is ...