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
1answer
27 views

Solve the recurrence of the alternating sum $R_n=R_{n-1}+(-1)^{n}(n+1)^{2}$

I have been trying to solve this recurrence for a few hours, but I haven't been able to find the solution yet: $R_0=1$ $R_n=R_{n-1}+(-1)^{n}*(n+1)^{2}$. I have been trying to substitute ...
0
votes
1answer
12 views

Induction Mathematics and Factorials

\usepackage{amsmath} Evaluate the sum $\sum_{k=1}^{n} {k\over (k+1)!}$ $\sum_{k=1}^{1} {1\over (1+1)!} = {1\over 2}$ $\sum_{k=1}^{2} {2\over (2+1)!} = {2\over 3}$ $\sum_{k=1}^{3} {3\over (3+1)!} ...
0
votes
1answer
27 views

Which discrete mathematics book do you think is better between Epp's and Rosen's for a clueless self-learner?

I am a programmer, and I want to become a machine learning researcher and a good software engineer. I dabbled with calculus, linear algebra, and real analysis for a few months when I was enrolled in a ...
0
votes
2answers
33 views

Proofing Induction Mathematics

I have just started to cover induction mathematics in my Discrete Mathematics class and I'm a little confused as to where to go with this problem. Am I on the right track? Prove that 9 divides (n^3 ...
2
votes
1answer
25 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
1answer
16 views

Does this recurrence relation run in $\theta$(n)?

This is the recurrence relation I am trying to solve $T(n) = 2T(\frac{n}{4}) + 16 $ $T(1) =c $ I broke down(solved this reurrence relation) to $\sqrt2*c*n + 32 * \sqrt2* n - 32$ which runs in tight ...
0
votes
0answers
6 views

what is the total number of ways Company can advertise meeting its minimum cost strategy

There are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money). Company strategy is that, they ...
-1
votes
1answer
27 views

Covering relation over functions

F is a group that includes all functions from N to N K is relation over F. For f,g ∈ F: (f,g) ∈ K iff ∀ n∈N, f(n)≤g(n). Obviously K is Partially ordered set and not Total Order. My problem is with ...
0
votes
1answer
18 views

Uniqueness in Mantel Theorem

In Mantel's Theorem: I know that $K_{\lceil n/2 \rceil , \lfloor n/2 \rfloor} $ achieves the maximum number of edges without having a triangle. But why is it the unique example?
0
votes
1answer
20 views

Calculating edge count of non standard shape(?)

So basically, I want to have a map of any size/proportion (locking it down to integers). e.g. $4 \times 4$ $\begin{matrix} 2 & 3 & 3 & 2\\ 3 &4 &4 &3\\ 3 & 4& ...
1
vote
0answers
22 views

The graph has an Euler tour iff in-degree($v$)=out-degree($v$)

I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2) A simple ...
-1
votes
0answers
5 views

how to use recursive version of MinSort,selection sort [on hold]

following algorithm is a recursive version of MinSort, or selection sort, which takes as input an array A of n integers and returns an array with the elements of A sorted from smallest to largest. ...
-1
votes
1answer
24 views

Prove that the given algorithm is correct for various cases. [on hold]

The following algorithm determines whether a word is a palindrome; that is, if the word is the same read left to right as right to left. Palindrome($s = s_1s_2s_3 \ldots s_n$) (a string of length ...
-4
votes
0answers
17 views

How to find recursive formaula for a ternary string [on hold]

A ternary string $12210021$ of length $8$. Let $T(n)$ be the number of ternary strings with the property that there is never a $2$ appearing anywhere after a $0$. For example, $12120110$ has this ...
-2
votes
1answer
26 views

how to find recursive formaula for airplane seats [on hold]

An airplane seat can either accommodate one person or two people, if one of them is an infant under the age of two. Seats can also be empty. An arrangement of people in a row of an airplane is a ...
-1
votes
2answers
24 views

How to find out the recursive formula for tromino tiling of a 3 × n rectangle

Say you are tiling a 3 × n rectangle with L-shaped tiles of area 3 (trominoes). (To tile the rectangle is to cover it with tiles so that no tiles overlap, no tiles are hanging off the edge of the ...
0
votes
1answer
32 views

Partition and equivalence relation

Consider the equivalence relation between non-empty subsets $A , B$ of $\{ 1,2,3, 4,\dots,100\}$ defined by the condition: the greatest element of $A$ is the same as the greatest element of $B .$ ...
0
votes
0answers
17 views

give the recursive structure of the following problems

A) When you cut a pie, you cut along a diameter of the pie. Let $P(n)$ be the number of slices of pie that exist after you have made $n$ cuts, where $n \geq 1.$ Write a recurrence for $P(n).$ B) In ...
1
vote
1answer
34 views

This question is from my discrete math. So far i have no idea how to solve it. Can anyone help me with this? [duplicate]

Let n be a prime. 1. If (G,+) has order 2n, prove that every proper subgroup of (G,+) is cyclic. 2. If (G,+) has order n^2, prove that (G,+) has a subgroup of order n.
0
votes
3answers
44 views

Number of elements in a set.

i am just getting started with discrete mathematics and set theory and i came across this question which would seem like an elementary problem. I would appreciate any help on this : Suppose $m$ and ...
2
votes
0answers
18 views

Inversion of a pairing function

I was reading this Question on this site and I saw that the following pairing function was mentioned (a modified version of Cantor function): $$\langle x, y\rangle = x * y + ...
0
votes
1answer
14 views

find transitive clouser of a matrix [on hold]

Find transitive closure of R if M_R is $$\begin{bmatrix}1 & 0 &0 \\0 & 1 & 1 \\1 & 0 & 1 \end{bmatrix}$$ I tried doing it like this M_R * M_R * M_R but could not get the ...
-3
votes
0answers
19 views

Bit String Probability [on hold]

Given a bit string of length 8 begins with a 0, find the probability that it contains exactly three 0's. How many bit strings of length 8 contain an evan number of 0's? How can permutations and ...
-4
votes
2answers
52 views

Proof By Induction [on hold]

I am trying to prove the Following, However, I dont understand what to do at the Inductive Step: Any Help would be appreciated!
4
votes
2answers
106 views

How do I prove that $ f(n) = (n + 1)! - 1 $ is an injective function?

I have this problem: Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by $$f(n) = (n+1)! - 1$$ Prove that $f$ is injective. How do I ...
0
votes
1answer
20 views

Bitstring Probability

I am not understanding how to apply n choose r and permutations to the following problem. Given a bit string of length 8 that has exactly three 0's, what is the probability that the bit string will ...
0
votes
1answer
13 views

How many comparisons are needed for a binary search in a set of 64 elements

Answer: So the recurrence relation for binary search is f(n) = f(n/2) + 2. ...
2
votes
1answer
36 views

calculating characteristic polynomial in $\mathbb{R}^n$

Given some hyperplane arrangement $\mathcal{A}$, we call any subset $\mathcal{B}\subseteq \mathcal{A}$ $\textit{central}$ if $$\displaystyle \bigcap_{H\in \mathcal{B}}H\neq \emptyset.$$ There is a ...
0
votes
1answer
25 views

Summation. Combining different set of indices.

I am reading the second chapter of Concrete Mathematics book and I cant get my head aroud a simple concept: it is stated there that $$ \sum _{k \in K} a_k + \sum _{k \in K'}a_k = \sum _{k \in K \cap ...
1
vote
1answer
48 views

There are 8 balls which appear identical. However, 1 is heavier than the rest. How do you find the ball with 2 weighings?

I understand there are similar problems but I am not sure how to go about constructing this problem with set of balls that are not exponents of 3^n. I know I need at least 2 weighings to find the ...
1
vote
1answer
32 views

Drawing Bijections for one set

I just want to make sure I understand what to do when asked to draw bijections. So when I am asked Draw the diagrams (as we did in class) for all bijections $f : A\to A$ when the set $A$ is $A = \{1, ...
0
votes
1answer
14 views

Suppose that E and F are events in a sample space … [on hold]

Suppose that E and F are events in a sample space and $p(E) = \frac{1}{3}$, $p(F) = \frac{1}{2}$, and $p(E | F) = \frac{2}{5}$. Find $p(F | E)$?
2
votes
1answer
27 views

Given the graph below, use Dijkstra’s algorithm to find the shortest path (More details included)

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: Here is the solution to that example: Now here is the ...
0
votes
1answer
29 views

$n$ divides $a_1 - a_2$ as well as $b_1 - b_2$. Show that $n$ divides $a_1b_1 - a_2b_2$.

I keep arriving at $a_1b_1$ and $a_2b_2$ having the same sign if I multiply the equations $a_1 - a_2 = nk$ and $b_1 - b_2= np$ times each other. They must be opposite signs so that I can say that $n$ ...
2
votes
2answers
35 views

Is this proof for 1/4 mod 9 = x, correct?

Find an integer x so (1/4) mod 9 = x Proof: ...
0
votes
0answers
10 views

Need a lower bound for a discrete monotonic distribution

I'm staring at the following expression: $$ \displaystyle \frac{\sum_{i=0}^{n}\sigma_i\left(\sigma_i-\sigma_{i-1}\right) w_i}{\sum_{i=0}^{n} \sigma_i^2}$$ I need to come up with a lower bound to ...
0
votes
1answer
16 views

Still stuck on simplifying terms while doing linear combinations

So I'm currently trying to wrap my head around finding gcd through the Euclidean Algorithm in order to write the integers as a linear combination. For example, a problem is to express the ...
1
vote
0answers
13 views

Verify combination of disjoint subsets $C$ and $D$ is onto

Let $C$ and $D$ be disjoint subsets of set $A$ and $f:C→B$ and $g:D→B$. Define a function $h(x)$ as follows: $$ h(x)=\left\{ \begin{array}{c} f(x) \textrm{ if } x∈C \\ g(x) \textrm{ if } x∈D ...
0
votes
1answer
15 views

Make the set $R$ transitive

Let $R$ be a relation on a set $A=\{w,x,y,z\}$ defined by $R=\{(w,x),(y,x),(x,y),(z,z)\}$. Using the original relation, $R$, make the necessary minimal additions to make $R$ transitive. I thought ...
2
votes
0answers
12 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
3
votes
3answers
228 views

How to prove this argument valid?

I was just wondering if some helpful person wouldnt mind helping me with this discrete maths question that has had be stuck for about a day now. The argument is: ...
-2
votes
2answers
27 views

N Choose K Problem: how many strings of length 8 with exactly five A's are there if characters are chosen from the letters A, B, C, D, E? [on hold]

how many strings of length 8 with exactly five A's are there if characters are chosen from the letters A, B, C, D, E?
4
votes
0answers
28 views

Proving $f$ cannot be onto

If $f$ maps finite sets $A$ to $B$ and $n(A) < n(B)$, prove that $f$ cannot be onto. Proof by contradiction: If $f: A→B$ and $n(A) < n(B)$, $f$ is onto. Since, by definition of a ...
1
vote
1answer
17 views

Repeated rules in Chomsky normal form

My question is simple, when you're converting a grammar to CNF, what happens when a rule begins to repeat multiple times? ¿It's good to end with rules like $U_1 \rightarrow SB, U_2 \rightarrow SB, ...
0
votes
0answers
37 views

How many strings $s^\infty$ with $s$ a string of length $\le k$ on alphabet $\{1,2,…,m\}$?

As a function of $k$ and $m$, say $f(k,m)$, how many strings are of the form $sss... = s^\infty$, where $s$ is a string of finite length $\le k$ on the finite alphabet $\{1,2,...,m\}$? E.g., ...
3
votes
1answer
41 views

Pigeon Hole Principle : For $n + 1$ numbers

My question is : Take $n + 1$ numbers out of $1, 2,..., 2n$ Show that there will be two consecutive numbers My Approach : Using the Pigeon Hole Principle , the $n$ holes are ...
1
vote
1answer
34 views

Am I right in this discrete mathematics question?

$A = \{0, 1, 2\}$ $B = \{x \in R\mid−1 \le x \lt 3\}$ $C = \{x \in R\mid−1 \lt x \lt 3\}$ $D = \{x \in Z\mid−1 \lt x \lt 3\}$ $E = \{x \in Z+ \mid−1 \lt x \lt 3\}$ I put that $A=D$, $A=C$, and ...
0
votes
1answer
17 views

How does simplification work when solving linear combinations?

So I'm currently trying to wrap my head around finding gcd through the Euclidean Algorithm in order to write the integers as a linear combination. For example, a problem is to express the ...