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
23 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
0
votes
2answers
54 views

Sets and Relations in Math

I have not knowledge about relations, could you help me to solve this excercise step by step, to use in futures excercices? Thanks for your time. Given the set $A = \{1, 2, 3, 4\}$ and $B = \{1, 3, ...
0
votes
0answers
27 views

Use the Chinese Remainder Theorem to show that an integer $a$, with $0 \leq a < m = m_1*m_2* \dots *m_n$, …

Question: Use the Chinese Remainder Theorem to show that an integer $a$, with $0 \leq a < m = m_1*m_2* \dots *m_n$, where the integers $m_1, m_2, \dots, m_n$ are pairwise relatively prime integers ...
1
vote
3answers
77 views

Counting valid tickets

I think my question is very easy but I need to understand. The problem is, I have a ticket with 2 numbers from 1 to 10. The first number cannot be greather than the second number. How many valid ...
1
vote
0answers
22 views

How do I prove this equality involving ceilings and max?

For all $T \in \mathbb{N}$ the following holds, with $k \in \mathbb{Z}$ and $m, n \in \mathbb{N}$: $$\left \lceil \frac{k \cdot m}{n} \right \rceil + T - 1 = \max_{0 \leq i < T} \left \{ i + T ...
0
votes
0answers
34 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
1
vote
1answer
29 views

Alternatives to absolute error?

Let me explain my scenario in which I need to calculate absolute error. Lets say the X is the actual value. And X' is the value of X with some error 'e'. So X' = X + e'. Lets say i = 1 to 10000. I ...
1
vote
0answers
31 views

Either or in compound statement

I think this might be a silly question, but I'm confused. Please help me to understand it. Statement is: Randy studies German on either Tuesday or Friday. How should I write this as compound ...
0
votes
2answers
52 views

Constructing a formule

Could you help me with that? \begin{align} 1 &= 1 \\ 1 - 4 &= -(1 + 2) \\ 1 - 4 + 9 &= (1 + 2 + 3) \\ 1 - 4 + ...
3
votes
5answers
905 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
2
votes
3answers
40 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
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 ;)
1
vote
1answer
79 views

Determining the different number of subsets (counting, permutations, combinations)

Given that any fixed integer n>0, let S={1,2,3,4,...,n}. Now a Red-Blue subset of S is called T. Every element of T is given a colour (either red or blue). For instance {17 (red)}, {1 (red), 5(red)} ...
3
votes
3answers
760 views

Fibonacci Numbers Proof

Prove the following fibonacci sequence, which appear in Pascal's Triangle. I am not sure where to start on this, any pointers? $$ f_n = {n\choose0} + {n-1\choose1} + ... + {n-k\choose k}$$ where ...
1
vote
1answer
62 views

Permutations, Combinations, and Counting

A group of 63 people are camping together. They have two 6-person tents, three 4-person tents, five 3-person tents, and three 2 person tents. 18 people will sleep outside of the tents under a tarp. ...
2
votes
1answer
57 views

How many answers can be created using the elementary arithmetic operators?

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)? These are the rules: All numbers ...
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$ ...
1
vote
1answer
90 views

Convert adjacency matrix to graph

Is there any online service that can provide possible graphs (the simplest one) when I give a sequence of integers (node degrees) as input (or reject the input) -based on Erdős-Gallai formula? Thanks ...
-1
votes
1answer
62 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
0answers
48 views

Solution of definite integral of product of bessel function and exponential

I have an integral $I=\int_{\theta} \int_r J_m(k_1r)e^{-j[P_x r \cos(\theta)+P_y r \sin(\theta)]} r dr d\theta$ $0\leq\theta\leq2\pi; r<\infty$ is there any method to solve this?
0
votes
1answer
57 views

What is the derivation of A not being a proper subset of B?

The exact question is actually "Derivation A ⊄ B", and I am assuming that derivation in this case means to prove and give an example of when this is true? If it is then A is not a proper subset of B ...
0
votes
2answers
48 views

Use the Binomial Theorem to show that $0 = \sum_{k=0}^ n (-1)^{k} {n \choose k }$ [closed]

Use the Binomial Theorem to show that "$$0 = \sum_{k=0}^ n (-1)^{k} { n \choose k}$$".
0
votes
1answer
37 views

$a \equiv b(\bmod m) \iff a \bmod m = b \bmod m$

$a \equiv b(\bmod m) \iff a \bmod m = b \bmod m$ My attempt: $a \equiv (\bmod m) \Leftarrow a (\bmod m) = b (\bmod m)$ $\exists q_1, q_2\in\mathbb{R} | (a = m*q_1 + r) \wedge (b = m*q_2 + r)$ ...
1
vote
1answer
52 views

Discrete math and rules of inference

I recently did this rules of inference/logic question and the method I used was different from the textbook so I was wondering if my work was correct?
0
votes
1answer
62 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
4
votes
2answers
37 views

Proving Induction $(1\cdot2\cdot3)+(2\cdot3\cdot4)+…+k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4$

I need a little help with the algebra portion of the proof by induction. Here's what I have: Basis Step: $P(1)=1(1+1)(1+2)=6=1(1+1)(1+2)(1+3)/4=6$ - Proven Induction Step: ...
2
votes
2answers
82 views

Solving the equation $n\log n = 10^9$

This seems very basic (I guess my calculus needs brushing up). Is there a way to find n without a calculator in this one? $10^{9} = n\log(n)$ My Attempt (log is base 2 base on the book convention.) ...
1
vote
1answer
67 views

The relationship between each harmonic numbers

In Knuth's "Concrete Mathematics" in chapter about numbers below equality is given $$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\epsilon_n}{120n^4} $$ where $0 < \epsilon_n < ...
2
votes
1answer
106 views

First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
0
votes
2answers
73 views

Show that $\binom{n}{k}< \binom{n}{k+1}$ if and only if $k < (n-1)/2$ [closed]

Show that $\binom{n}{k} < \binom{n}{k+1}$ if and only if $k < \frac{n-1}{2}$ and then use this to deduce that the maximum of $\binom{n}{k}$ for $k=0,1,\dots,n$ is $\binom{n}{\lfloor ...
0
votes
0answers
17 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
4
votes
1answer
81 views

Closed form of $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$

Recently, I came across the following exercise on the course of discrete math Find a closed form for $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$ So I tried some of the usual techniques: Let ...
1
vote
5answers
53 views

discrete mathematics and proofs

Let $a$ and $b$ be in the universe of all integers, so that $2a + 3b$ is a multiple of $17$. Prove that $17$ divides $9a + 5b$. In my textbook they do $17|(2a+3b) \implies 17|(-4)(2a+3b)$. They do ...
3
votes
1answer
34 views

how many ways can 1001 people win 500 identical items?

the question is stating that $1001$ people are in a race and there are $500$ objects that are identical (say the same shirts). We need to find the number of ways that the 500 shirts can be given out ...
2
votes
1answer
48 views

Proof Verification for Discrete Math Class

Prove that $n^2$ is even iff $n$ is even. I proved it like this: Case I: $n$ is even 1) $n = 2a$ $(a\in Z)$ 2) $n^2 = 4a^2 = 2(2a^2)$ 3) $2a^2 = K$ $(K \in Z)$ 4) $n^2 = 2K$ Case II: $n$ is ...
1
vote
1answer
56 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
1
vote
1answer
43 views

Mathematical induction of the harmonics number

My textbook has the steps to prove it, but I can't comprehend the steps that the textbook are showing. Can someone explain the math or logic used going from steps red to yellow and finally green?
9
votes
1answer
131 views

How many Sudoku puzzles are there with at least one solution?

A Sudoku puzzle is a 9 by 9 matrix of blanks(which we can represent as 0), and elements of the set {1,2,3,4,5,6,7,8,9}. How many Sudoku puzzles are there with at least one solution. Yes, I am even ...
0
votes
0answers
78 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
2
votes
2answers
77 views

What are a geometric system and a finite geometry?

Wikipedia says A finite geometry is any geometric system that has only a finite number of points. I wonder what a geometric system is? Is it some set system $(E, F)$, where $E$ is a set and $F ...
0
votes
2answers
83 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
56 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
2
votes
2answers
82 views

Initial value of Newton Raphson Method

I am currently studying Newton-Raphson Method. I feel that I understand the concept of it. Somehow, I am facing some question in my head about how to actually apply it. The questions that I have are ...
0
votes
3answers
45 views

How do I finish this summations problem?

I have posted a picture since I don't know how to make the summation symbols with the lower and upper summations on keyboard, sorry about that.. $$\sum_{a=1}^9\sum_{b=0}^9(101a+10b)$$ The answer is ...
0
votes
1answer
130 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
0
votes
1answer
43 views

How to test mathematically if a number contains the highest digit of its radix?

Is there a way to test mathematically if a number contains the highest digit of its radix, and if so how? For example, 101 in base 2 contains the digit 1, highest in base 2; but 101 in base 3 does ...
2
votes
6answers
528 views

Discrete math induction problem.

I am stuck at this step in the inductive process and I was wondering if someone can help me out from where I am stuck. Question: if $n$ is a positive integer, prove that, ...
0
votes
3answers
108 views

Giving an equivalence relation that corresponds to set partitions

My question is: Give equivalence relation that corresponds to the partitions A1 = {1,3,5} A2 = {2} A3 = {4,6} of the set A = {1,2,3,4,5,6} I don't know what the format of the relation should be, in ...
8
votes
5answers
181 views

Does $\{1,2,\ldots,3000\}$ contain a subset of $2000$ integers with no member twice another?

Does the set $X=\{1,2,\ldots,3000\}$ contain a subset $A$ of $2000$ integers in which no member of $A$ is twice another member of $A$? I started by putting $P=[1501,3000]$, but twice any integer in ...
1
vote
2answers
58 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...