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
3answers
131 views

Proving that $aRb \iff a^2-b^2=a-b$ is an equivalence relation

Could you help me with that, I don't know how to prove if the relation is an equivalence and the class of 5? On the set of integers, the relationship is defined by $aRb \iff a^2-b^2=a-b$. Find out ...
0
votes
7answers
172 views

$\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$

Show that $\,\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to ...
0
votes
6answers
3k views

Finding the number of subsets of S

How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6? Thanks!
0
votes
2answers
92 views

How do evaluate $x = (5^2 \bmod 6)^4 \bmod 15?$

$x = (5^2 \bmod 6)^4 \bmod 15$. I wanted to turn $(5^2 \bmod 6)^4 \bmod 15$ into a constant, but I just lost hope when I saw how humongous the expression was.
0
votes
3answers
1k views

Proof that every odd integer is a difference of two squares [duplicate]

How can I use a direct proof to show that every odd integer is the difference of two squares?
0
votes
4answers
112 views

Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$. (Big-o notation) [closed]

Will someone help me prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$? Thank you.
0
votes
5answers
109 views

Count of all combinations of a set

All right, sorry in advance if this exists on here already. What I'm after is figuring out all possible orders of a set. So I have 2 items 1,2 2,1 =2 3 items ...
0
votes
2answers
659 views

Explain this paradox

Can someone help me explain this paradox please. A simple harmonic oscillator $ma=-kx$ is a system that oscillates in one dimension. But the text book says one-dimensional system can't oscillate. Why ...
0
votes
3answers
842 views

Analytical Reasoning Question II

I have yet another analytical question that got me A five-digit number is formed using digits 1, 3, 5, 7 and 9 without repeating any one of them. What is the sum of all such possible numbers? ...
0
votes
3answers
191 views

Find two sets $A$ and $B$ such that $A$ is an element of $B$ and $A \subseteq B$.

Find two sets $A$ and $B$ such that $A$ is an element of $B$ and $A \subseteq B$. Would $A = \{1,2,3\}$ and $B = \{1,2,3\}$ work? Any help?
0
votes
3answers
374 views

Mathematical induction prove that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ .

How can I use mathematical induction to prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a nonnegative integer?
0
votes
4answers
74 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
0
votes
4answers
2k views

Modular arithmetic (Solve -10 mod 7 by hand)

For: -10 mod 7 I know the answer is 4, but how do you actually get to the answer by hand?
0
votes
2answers
60 views

Flipping a fair coin until either H or TTTT appears; what is the probability of getting at most two T's?

We flip a fair coin repeatedly and independently, resulting in a sequence of heads (H) and tails (T). We stop flipping the coin as soon as this sequence contains H or T T T T. What is the probability ...
0
votes
3answers
108 views

Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N ex ...
0
votes
2answers
50 views

Contrapositive Proof: Specific Question! Need help!

I've been stuck on this question for a few days, please help me with this contra positive proof! Suppose that $x$ and $y$ satisfy $\frac 1 2 x + \frac 1 3 y = 1$. Prove that $x^2 + y^2 > ...
0
votes
2answers
165 views

Non-trivial finite/infinite subgroups of infinite groups

Does an infinite group whose every non-trivial subgroup is also infinite exist? If yes, what can be an example of such a group? also, Does an infinite group whose every non-trivial subgroup is ...
0
votes
3answers
140 views

How to determine countability of $\Bbb N \times \Bbb N \times \Bbb N$?

Is $\Bbb N \times\Bbb N \times\Bbb N$ countable or not, where $\Bbb N$ is the infinite set of all natural numbers ? Please explain how it is done.
0
votes
5answers
1k views

Proving any product of four consecutive integers is one less than a perfect square

Prove or disprove that : Any product of four consecutive integers is one less than a perfect square. OK so I start with $n(n+1)(n+2)(n+3)$ which can be rewritten $n(n+3)(n+1)(n+2)$ After multiplying ...
0
votes
4answers
140 views

Why is $n^2 - 2$ never a multiple of $3$?

I know that for any $n$, $n^2 - 2$ is never a multiple of $3$. I feel like this is a rather simple proof, but I cannot figure out how to manipulate the definition of a multiple of $3$: $n$ is a ...
0
votes
3answers
76 views

(Dis)prove that: $\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$

So I'm trying disprove this statement. Well, I'm pretty sure it's wrong because it doesn't work when $a = 0$ . I'm just not sure if all I need to do is give that counterexample, or if there is a way ...
0
votes
2answers
7k views

Basic Equivalence Class Discrete Math

I read through the textbook definition, but still cannot clearly understand what an equivalence class is Does anyone have a good example with a definition that can hit me home?
0
votes
2answers
629 views

Proof that there are infinitely many Ulam numbers

This is part of self-study; this question is taken from "Discrete Mathematics and Its Applications" (Rosen). We define the Ulam numbers by setting $u_1$ = 1 and $u_2$ = 2. Furthermore, after ...
0
votes
2answers
115 views

binary subtraction

I am trying to solve binary subtraction: $$11000_2 - 1011_2 = 1001_2$$ I know that it should be $1001_2$, when checking with answer key however I am not sure how it was calculated as I get different ...
0
votes
2answers
43 views

Prove the result is always a rational number

I am trying to prove the following: If $a$ and $b$ are non-zero rational numbers, then $a^{b}$ is rational. Any ideas or hints how to prove this?
0
votes
3answers
67 views

Is it true that every injective function must be surjective? [duplicate]

I believe it is false, because an injective function never maps elements of the domain to the same element of its codomain, where as the surjective function can map an element of the codomain to any ...
0
votes
4answers
75 views

Math expression with potencies always 13 multiple

Hello my question is simple: How can I prove that $$4^{2n+1}+3^{n+2}$$ is always divisible by 13? Thanks for your time ;)
0
votes
2answers
46 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
0
votes
6answers
64 views

Prove that for all positive integers $n, 9|(11^ n − 2 ^n )$

Prove that for all positive integers $n, 9|(11^n − 2^n )$ So the base case would be 9 * k = (11*1 - 2 * 1) 9 * k = 9 k = 1 so yes The inductive hypothesis ...
0
votes
3answers
64 views

Homework question. please give me hints or feedback

Prove or find a counterexample: For all real numbers x and y it holds that x + y is irrational if, and only if, both x and y are irrational
0
votes
2answers
46 views

Calculate the $26$ term for the generating function.

Let $\lambda x.(1+x+x^{10})^{20}$. What is the the $26$ term for the series generated by this function? Thanks.
0
votes
5answers
82 views

$4011x+42053 \equiv 2x-782398 \pmod {10}$

$4011x+42053 \equiv 2x-782398 \pmod {10}$ $10|(4011x+42053-2x+782398) \space \rightarrow \space 10|(4009x + 824451)$ $\rightarrow\space 4009x\equiv -824451 \pmod {10}$ I am dubious about this next ...
0
votes
4answers
68 views

Prove that $(A^c \cup B^c) - A = A^c $

Prove that for any two sets A,B, we have $(A^c \cup B^c) - A = A^c $ Attempt Let $x \in\ (A^c \cup B^c) - A$ Then, $x \in\ A^c$ or $x \in\ B^c$ and $x \notin\ A$ $x \in\ A^c$ or $x \in\ B^c$ and ...
0
votes
5answers
129 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
0
votes
2answers
92 views

If $B \subseteq A$ and $f:A \to B$ is 1-1, it must be onto

Let $B \subseteq A$ and $f: A \to B$ be a 1-1 function, then $f$ must be onto. I understand that $f$ is onto if and only if every element of $B$ is in the image of $f$... I believe this ...
0
votes
2answers
42 views

For all integers $m$ and $n$

Prove or disprove: For all integers $m$ and $n$, if $m+n$ is even then so is $m-n$. Would you just set them even to each other because you are given $m+n$ is even?
0
votes
2answers
72 views

Mathematical notation help.

Is saying !(6 = 4k) a right way to express that 6 is not divisible by 4? Or is there a better more accepted way? I'm writing a proof for discrete math and I need to be sure I'm doing it right.
0
votes
3answers
115 views

How to find floor $\frac{(x+\frac{1}{2})} {x}$?

Not sure how to figure out this...I tried just doing normal $\frac{(x+\frac{1}{2})} {x}$ but I know that's not solving for the floor and I know I need a squeeze theorem..but not sure how to solve ...
0
votes
3answers
161 views

How does one do this question? Find the smallest integer $k$ such that $\exists n\in\mathbb Z$ with $2^{10}\cdot3^4\cdot5\cdot k = n^6$

Find the smallest integer $k$ such that $\exists n\in\mathbb Z$ with $2^{10}\cdot3^4\cdot5\cdot k = n^6$. I have no sweet clue how to do this question.
0
votes
2answers
718 views

Is it true that every positive integer is the sum of 18 fourth powers of integers? (No, but i don't understand given answer)

My question is actual at the bottom in bold and is about the logic the author uses. Is it true that every positive integer is the sum of 18 fourth powers of integers? This is a question form a ...
0
votes
2answers
53 views

Prove $k\binom{n}{k} = n\binom{n-1}{k-1}$

The Problem: I want to prove $k\binom{n}{k} = n\binom{n-1}{k-1}$ algebraically My Work So Far: $n\binom{n-1}{k-1}$ $= n(\frac{(n-1)!}{(k-1)!(n-k+1)!})$ (By definition of $\binom{n-1}{k-1}$) $= ...
0
votes
1answer
28 views

How to tell if the following function is one to one

Let f:A→B where A = X∪Y with X∩Y=∅. If f|x and f|y are one-to-one, does it follow that f is one-to-one? I am unsure how to figure this out. I have gathered from the info provided that X and Y are ...
0
votes
3answers
35 views

Combinatorial problem - multisets

As I am solving some basic combinatorial problems today, I found out this problem: How many different 5-digit numbers can be formed from digits 2, 2, 7, 7, 9? Can someone guide me to a solution for ...
0
votes
2answers
89 views

combinatorial proof of summation

Prove $\sum_{i=1}^n2^{i-1}=\sum_{i=0}^{n-1}2^i=2^n-1$ combinatorially. This is easy to prove inductively. I know that $\sum_{i=0}^n{n\choose i}=2^n$ so maybe change $\sum_{i=0}^{n-1}2^i$ to ...
0
votes
3answers
83 views

Prove that $n = 2a + 3b$.

How can I prove by induction that for any natural number $n$ there exists integers $a,b$ so that $2a+3b=n$ I can prove the base case, and I can imagine why it works but how can I prove it ...
0
votes
3answers
39 views

Need to check if this function is bijective

I don't understand how $f : \mathbb N \to\mathbb N$ (where $0$ isn't included in the natural numbers set), $f(n) = n^2$ is not bijective. It seems both injective and surjective to me? Thanks got it!
0
votes
2answers
51 views

Why is $n\log(n^2 + 1)=O (n\log n)$ instead of $O(n\log n^2)$?

Why is $n\log(n^2 + 1)=O (n\log n)$ instead of big $O(n\log n^2)$? I thought all I needed to do was drop the constant and just write the big O of what remains. How did $O(n\log n)$ came out of ...
0
votes
4answers
103 views

How many four digit numbers are there?

Assume that 0 can't be a first digit. I got 9,000. Is that right? Follow up question: How many of those four digit numbers have no repeated digits?
0
votes
2answers
4k views

How many positive integers less than 1000 are divisible [closed]

How many positive integers less than 1000 c) are divisible by both 7 and 11? d) are divisible by either 7 or 11? e) are divisible by exactly one of 7 and 11?
0
votes
3answers
168 views

Why does $0,\bar{9}$ equal $1$? [duplicate]

I am finding hard to understand why $0,99999..... = 1$ I have the following proof: Let $x$ be $0,9999...$ then $10x = 9,999...$ So $10x - x = 9,999 - 0,9999$ $9x = 9 \rightarrow x = 1$ From a ...