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
votes
0answers
35 views

A fair die is tossed twice. Let Z be the sum of the tosses and W be the difference.

A fair die is tossed twice. Let Z be the sum of the tosses and W be the difference. Are Z and W independent? Explain.
2
votes
2answers
30 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
17 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
28 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
49 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
44 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, ...
1
vote
4answers
80 views

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

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$?
0
votes
1answer
43 views

Is the following statement true? if so prove. ∃ a,b ∈ R, ∀x ∈ R, (ax+b=x)

Is the following statement true? if so prove. $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$ Having a hard time proving this statement.
0
votes
2answers
54 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
39 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
18 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.
0
votes
4answers
75 views

Prove for each $n\in \mathbb{N}, 1^3 + 2^3 +\cdots+ n^3 = \frac{n^2(n+1)^2}{​4} ​ ​​​$ [duplicate]

So I was given a proof by induction question and here is my attempt $$1^3 + 2^3 + 3^3+\cdots+n^3= \frac{n^2(n+1)^2}{4}$$ $n=1$ $1=1$ Induction step: Assume statement is true for $n=k$, show true ...
0
votes
3answers
58 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
28 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
633 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
35 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
30 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
98 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
53 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
109 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
33 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
76 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
79 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
94 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
44 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
28 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
50 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
46 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
69 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
38 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
39 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
57 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
433 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
34 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
23 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
44 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
29 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
391 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
57 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
81 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
45 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 ...