Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
1answer
16 views

using multinomial theorem to expand ($2x -y + 3z)^3$

I know how to set it up and there is for this example $10$ terms. But what is the best way to find the expanded work plus finding the final answer? Sorry if there is a duplicate to this problem. I ...
0
votes
2answers
17 views

Prove that there are no integer solutions to a given equation

Prove that $ 4x = y^2 + 1 $ has no integers solutions for $(x,y)$ By rules of divisibility: $$ a \mid b \implies \frac {b}{a} = n $$ for $a,b,n \in \mathbb{Z}$ So let, $ a=4x$, $b=y^2$, and $ c ...
-2
votes
2answers
44 views

Using Newton's binomial theorem to prove that a sum evaluates to $36^n-26^n$

Using Newton's binomial theorem to argue that: $n \ge 1$ $$36^n - 26^n = \sum_{k=1}^{n}\binom{n}{k}10^k \cdot 26^{n-k}$$ my argument $$(26+10)^n = ...
2
votes
2answers
19 views

How to prove a polynomials roots are integers?

I'm having trouble finding a direct way to prove questions like the following: $$ \exists x\in\mathbb{Z} |x^2+x=271 $$ Now, I know this is false, because $$x^2+x-271=0$$ $$x= ...
0
votes
0answers
13 views

Criticise work with simple graphs & problem solving

So I'm studying graph theory at the moment and would like some constructive criticism or thoughts on my method. The problem can be formulated as follows. I'm looking for someone to verify my answer as ...
-1
votes
2answers
29 views

Verify the Identity [duplicate]

$\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$ So far I have gotten $\frac{n!}{(k-1)!\big(n-(k-1)\big)!} + \frac{n!}{ k! (n-k)!}$ But I quickly lose myself once I have to start making the ...
0
votes
1answer
26 views

How to write a formal proof of the statement: For all real numbers $x$, if $x \ge 1$ then $\frac{3|x-2|}{x} \le4$

For all real numbers $x$, if $x\ge1$ then $\frac{3|x-2|}{x} \le 4$ I understand that I must algebraically show how to build on $x\ge1$ to reach $\frac{3|x-2|}{x} \le4$, but cant for the life of me! I ...
2
votes
1answer
30 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
1
vote
1answer
21 views

Solving a recurrence using the Master Theorem where $f(n) = log(\log n)$

I have the recurrence $$T(n) = 3\,T(n/2) + \log(\log n)$$ I take $a = 3$, $b = 2$ and $f(n) = \log(\log n)$. I also have $\log_2 3 = 1.585$. I'm not sure how to approach a log inside of a log. Would ...
0
votes
0answers
14 views

How many ways can 4 hands of 5 cards be selected from a deck of 52 cards?

1) How many ways can 4 hands of 5 cards be selected from a deck of 52 cards? 2) How many ways can 4 hands of 5 cards be dealt to 4 people?
0
votes
0answers
12 views

Applying Lovász local lemma, how to fix this solution

We have U - a "small" graph, which is fixed. The goal is to find a coloring(with d colors) of the edges of the complete graph with n vertices($K_n$, n-fixed), without monochromatic copy of U. We also ...
0
votes
2answers
47 views

How to prove that for all $x$ there exists some $y$ where $ (x^2 + y^2 \geq 0)$?

How can I prove that $\forall \,\,x\,\,\exists y\,\,,(x^2 + y^2 \geq 0)$?
0
votes
1answer
21 views

Combinatorial Proof: How many length-n lists can we form using the elements in {1,2,3} [PROOF]

I'm trying to prove that $2\times(3^0) + 2\times(3^1) + 2\times(3^2) + \cdots+ 2\times(3^(n-1)) = 3^n - 1$ by answering the question "how many length-n lists can we form using the elements in ...
0
votes
2answers
17 views

How many ways to form a committee?

Suppose there is a group of 7 Republicans, 6 Democrats, and 4 Independents. How many ways are there to form a committee with 6 members, if it must have at least 4 Republicans? So I took C(7,4) * ...
0
votes
1answer
15 views

Slack variable and counting integer solutions

So, I'm now familiar with the stars and bars method, but something struck my mind. To calculate non-negative integer solutions to $x_1+x_2+x_3+\cdots+x_n = k$ we use the Stars and Bars method. ...
1
vote
2answers
35 views

How many balls can be selected?

A sack contain 20 identical red balls, 20 identical blue balls, and 20 identical green balls. In how many distinct ways can 10 balls be selected from the sack?
2
votes
2answers
34 views

Combining four distinct objects with repetition

With four different objects $k = \{obj1, obj2, obj3, obj4\}$. How many combinations are there if I were to copy $20$ freely-chosen objects. I could for example have $20\times obj1$ if I wanted. ...
0
votes
0answers
12 views

Algorithm to answer questions on dominated input

Consider a setting where we see inputs one-by-one, with each input being an $n$-tuple $(a_1,a_2,...,a_n)$, where each $a_i\in\{0,1\}$. For each new input we see, we have to answer two questions: 1) ...
0
votes
1answer
30 views

A counting problem on the integer lattice

Let $K$ be a subset of the integer lattice $\mathbb Z^2$such that it contains elements of the form $k=(k_1,k_2) $ where $k_1,k_2$ are integers and $k_2\neq 0$. Find $m$, an integer if possible, such ...
1
vote
1answer
20 views

Verify my thought process on permutations

If there are $15$ distinguishable objects; all will be placed into $2$ boxes. There needs to be at least one object in each box. How many ways can you place these objects into the $2$ boxes? Tried ...
0
votes
1answer
29 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
1answer
42 views

The composition of functions and inverse of a set?

I'm a bit confused on how to do some of my discrete math work. I tried doing all of the problems, but I feel like I'm doing something wrong. If anyone could correct me, it would be greatly ...
0
votes
2answers
17 views

Propositional Logic Riddle, need help answering

I have attached below a propositional logic riddle that I am having difficulty solving. It would be great if one of you could post a solution to this problem with some clear and concise explanations ...
-2
votes
0answers
39 views

How do I classify this binary relation? [on hold]

Let $R$ be a binary relation with $R = \,f(x; y) \in \mathbb Z \times \mathbb Z$. There exists $k \in \mathbb Z$ such that $y = kx$. Is $R$: reflexive, symmetric, transitive. not ...
1
vote
1answer
29 views

Help solving first order discrete differential equation.

I am trying to solve the 1st order ODE, $x[k+1] + \frac14 x[k] = k\left(-\frac12\right)^k , k>= 0$. I have figured out the homogeneous solution to be $x_{h}[k] = \alpha\left(-\frac14\right)^k$, ...
1
vote
0answers
12 views

How do I derive the properties from a relation from the associated matrix?

Would anyone be able to help me answer this question? Let $A=\{1,2,3,4,5\}$ and $R$ be the relation on the set $A$ whose matrix is $$M_R = \begin{bmatrix}1 & 0 & 1 & 0 & 1 \\ 0 ...
0
votes
1answer
41 views

Combinatorics Question Help; # of ways to choose 4 distinct officials from a city?

there are $n \ge 4$ people in a city. And the city has its officials, consisting of 1 mayor and 3 vice-mayors. The entire board consists of 4 distinct students. Prove that by counting. In 2 different ...
-1
votes
0answers
7 views

Where can I find Assignments solution of the MIT course Mathematics for computer science? [on hold]

I'm studying MIT Course Mathematics for computer Science and I've been looking for the solution of the problems sets of the course in order to grade myself. But I haven't found anything so I'm asking ...
2
votes
0answers
26 views

Prove the big theta

I need to find a $n_0$ and $k$ for Big Oh and an $n_0$ and $k$ for Big Omega, to find a big theta bound for: $5n^2 - 9n = \theta(n^2)$ Can anyone help me and show me how to find these for this ...
3
votes
3answers
57 views

divisibility of number of solutions of $x_1+\cdots+x_k=n$

I observed that the number of solutions in positive integers $x_1,\ldots,x_k$ of $$x_1+\cdots+x_k=n$$ for fixed $k$ and $n$ is always a multiple of $k$ as long as $\gcd(k,n)=1$. For example, ...
0
votes
3answers
42 views

Showing that a composite function is bijective.

Can i straight away claim that $\varphi : T \rightarrow X$ is injective, and if $f:X \rightarrow Y$ is injective, then this means $f \circ \varphi : T \rightarrow Y$ is injective for as well any set T ...
0
votes
0answers
25 views

Problems involving showing function f is injective with phi and psi post and pre compose to function f

The 1st question goes that a map of sets f:S -> Z is injective if and only if for any set Q, the map Maps(Q,S) -> Maps(Q,Z), ϕ |-> f o ϕ of "post-composition with f" is injective. My solution is that ...
0
votes
1answer
33 views

mathematics probabilities help [on hold]

I have 5 random numbers from 5 to 50. I don't know how to solve this question. Consider a random collection of $n$ individuals in a room. Suppose $P_n$ symbolizes the probability to have at least ...
0
votes
0answers
47 views

Showing the map of post and pre composition ϕ and psi respectively with f is injective

(a) Show that a map of sets f:X->Y is injective if and only if for any set T, the map Maps(T,X) -> Maps(T,Y), ϕ |----> f o ϕ of "post-composition with f" is injective. (b) Show that ...
0
votes
2answers
24 views

Permutation and combination related question

My question is: Starting from Washington, DC, how many ways can you visit 5 of 50 state capitals and return to Washington? I tried to solve it, Firstly, we should choose 5 states from 50 countries ...
0
votes
1answer
39 views

Mapping and preimage

Just to clarify, ∪c∈c" c , the c∈c" is below the union ∪. P(Y) is the power set of Y. Let f : X -> Y be a map. (a) Show that for any subset C ⊆ Y , one has $f^{-1}$ (Y\C) = X\ $f^{-1}$(C) (b) ...
1
vote
1answer
19 views

Is there a proof for what I describe as the “recursive process of mathematical induction for testing divisibility”.

I was working on my homework for Discrete Math, and we were asked to "Prove: $6 | n^{3}+5n$,where $n\in \mathbb{N}$" my solution varied significantly from how I have seen it done by others. I noticed ...
0
votes
1answer
41 views

Big Theta Proof Tightness

I found that $n_0 = 1 $ and $k=5$ for Big Oh, but I am somewhat confused on how to prove big omega as I have a negative sign in my expression. Furthermore by showing big oh and big omega, am I showing ...
0
votes
1answer
47 views

Use induction to prove that a function is not one to one

Suppose that m and n are positive integers with m > n and f is a function from $\{1, 2,\ldots, m\}$ to $\{1, 2, \ldots , n\}$. Use mathematical induction on the variable n to show that f is not ...
-2
votes
0answers
36 views

Prove using Induction $ i(T) \leq 2^{h(t)} - 1$ in a full binary tree

Recursive Definitions for Full Binary Tree The height of a full binary tree, written $h(T)$, is dened recursively as follows. $h(T) = 0$ $h(T1 \cdot T2) = 1 + $max$\Big(h(T1), h(T2)\Big)$ The ...
1
vote
1answer
87 views

Prove this equality by using Newton's Binomial Theorem

Let $ n \ge 1 $ be an integer. Use newton's Binomial Theorem to argue that $$36^n -26^n = \sum_{k=1}^{n}\binom{n}{k}10^k\cdot26^{n-k}$$ I do not know how to make the LHS = RHS. I have tried ...
1
vote
2answers
62 views

Prove $1(1!)+\dots+n(n!) = (n+1)!-1$ using induction

So I'm trying to prove this statement (through induction): $$1(1!)+2(2!)+\dots +n(n!)=(n+1)!-1$$ But I'm confused with the inductive step here: $$(n+1)!-1+[(n+1)(n+1)!] = (n+2)!-1$$ What do I do ...
-2
votes
0answers
64 views

Prove h(T) = log2l(T) in a complete binary tree using Induction

Recursive Definitions for Full Binary Tree The height of a full binary tree, written h(T), is dened recursively as follows. h(T) = 0 h(T1 T2) = 1 + max(h(T1); h(T2)) The number of nodes in a full ...
0
votes
1answer
49 views

Prove Complete Binary Tree using Induction

Recursive Definitions for Full Binary Tree The height of a full binary tree, written h(T), is dened recursively as follows. h(T) = 0 h(T1 T2) = 1 + max(h(T1); h(T2)) The number of nodes in a full ...
0
votes
2answers
48 views

Find the largest natural number m such that n$^3$-n is divisible by m for all n$\in$ $\mathbb{N}$.

Find the largest natural number m such that n$^3$-n is divisible by m for all n$\in$ $\mathbb{N}$. Prove your assertion. So my basis that I have is: Notice that (1)$^3$-(1)=0, and m(0)=0, so m ...
0
votes
3answers
54 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
1answer
19 views

How to find number of disctinct functions from set A to set B

Let's say there is set A {1, 2, 3} and set B {a, b} While, I know that to find the total number of functions, it's just number of elements from B ^ number of elements from A But I just don't ...
0
votes
1answer
65 views

Please explain this explanation to me; Discrete Math: Counting

This is a counting solution to which selections of object which are not all distinct. The basic premise is that the number of non-negative integer solutions to $x_1+x_2+x_3+...+x_k = n$ is equal to ...
0
votes
0answers
12 views

Diophantine equation with three variables

I'm trying to solve a diophantine equation with $3$ variables. The problem can be written as a system of equations: $\begin{cases} 0.5x + 4y + 9z &= 97 \\ x+y+z &= 34 \end{cases} \implies ...
0
votes
0answers
14 views

Summation for the “selection sort algorithm”

Sorry if the title was not clear enough. I noticed this summation in a textbook (analysis of the Selection Sort algorithm) $C(n) = \sum_{i=0}^{n-2}\sum_{j = i + 1}^{n-1} 1 = \sum_{i=0}^{n-2}{(n-1 - ...