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
2answers
108 views

Prove (members of a recursive set) by structural induction

Trying to prove, using structural induction only, that every member of the following recursively defined set 𝑆 has a remainder of 1 when divided by 4 $1 ∈ 𝑆$ $𝑛 ∈ 𝑆 β†’ 5𝑛 ∈ 𝑆$ $𝑛 ∈ 𝑆 β†’ 𝑛^2 ...
2
votes
1answer
66 views

propositional logic , writing the statement in terms of propositional variables

I came across this question while practicing propositional logic Consider the argument: β€œIf Anna can cancan or Kant can’t cant, then Greville will cavil vilely. If Greville will cavil vilely, Will ...
2
votes
2answers
103 views

Nice Question in Mathmatics about Times

I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam. if the time is "Wednesday 4 ...
3
votes
5answers
1k views

Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

I am trying to prove the summation formula using induction: $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$ So far I have... Base case: Let n=1 and test $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$ ...
0
votes
1answer
53 views

Lattice which is not bounded lattice

I want to find an example of a lattice which is not a bounded lattice . Diagrams would be good with an explanation .
0
votes
1answer
126 views

Combinatorics: ways to place books

So we're trying to partition {1..n} into m ordered sets. I would do this by first scrambling {1..n} into one of n! orderings. After having done that we can partition that into m non-empty sets in ...
0
votes
1answer
123 views

What does the ${\uparrow}{\uparrow}$ symbol mean?

The question asked is calculate the value of: $\dfrac{2\mathbin{{\uparrow}{\uparrow}}3}{2^{100}}$ and I have no idea what the ${\uparrow}{\uparrow}$ symbol means.
1
vote
1answer
51 views

discrete math basic question

Al has 75 days to master discrete mathematics. He decides to study at least one hour every day, but no more than a total of 125 hours. Assume Al always studies in one hour units. Show there must be a ...
1
vote
2answers
46 views

Are these graphs isomorphic?

Are these 2 graphs isomorphic? (sorry for the bad picture quality) For the solution: 1) They both have 8 vertices 2) They both have 12 edges 3) They both have 8 vertices of degree 3 4) Is this ...
1
vote
2answers
41 views

An expression is divible by 4 but not 8.

Let $n\in\mathbb{N}$. Show that $4\mid(3^{2n+1} + 5^{2n})$ and $8\nmid(3^{2n+1} + 5^{2n})$ $(2m+1)^n = (2m+1)_1(2m+1)_2...(2m+1)_n$. Here I'm trying to show that an odd number raised to any integer ...
1
vote
2answers
28 views

recurrence equations. solve the equation

Solve the following recurrence equation $a_0=0, a_1=7$, and $$a_n=\frac{1}{3}a_{n-1}+\frac{4}{3}a_{n-2}, n\geq2$$ I have tried using the general method, however i am getting the same thing as $a_n$ ...
1
vote
1answer
101 views

Natural Number (Recursion Theorem)

For any natural number $a ∈ N$ , the exponential map of base $a$ is the map $a^ {( )} \mathbb{N} \rightarrow \mathbb{N}$, $n \mid \rightarrow a^n$, defined recursively (using the recursion ...
1
vote
2answers
639 views

Using Rules of Inference to imply conclusion

This is Discrete Math. I just learned how to use the rules of inference and I'm not sure if im doing this right at all. The question is: Use rules of inference to show that the hypotheses "If it ...
0
votes
1answer
43 views

What are the total number of ordered permutations of a list of elements (possibly repeated)?

This question is a part of a TopCoder problem. I am learning algorithms, and just got stuck at this (not homework). Suppose we have a set $A$ of integer elements, such that $n(A) = a$ (number of ...
0
votes
3answers
48 views

Why is this Relation R (graph) not transitive?

Let the arrow graph of R be the following: If we get the ordered pairs we have that R = { (a,a), (a,b), (a,c), (b,b), (b,a), (b,c), (c,a), (c,b), (d,d) } If we analyze this: *Reflexive - NOT ...
0
votes
1answer
76 views

Set of ordered pairs of the transitive closure R* of R

I pretty much know how to get the ordered pairs by doing the arrow graph method since the matrix method is much more complex. let R be: R = { (a,b), (b,a), (a,c), (c,d), (c,e), (e,c) } (I am ...
1
vote
2answers
37 views

Curiosity - maximising a product with a constraint

I have integers greater than 4, for instance $i_1$, $i_2$, $i_3$, ..., $i_n$. We have to change the greatest of these integers (for instance $i_1$ if they are ranked by descending order) by adding to ...
2
votes
2answers
53 views

Discrete mathematics vs. non parametric statistics

Is there any meaningful connection betveen non parametric statistics and discrete mathematics? I am reading this book: ...
0
votes
2answers
74 views

Chevalier de Méré's Problem Type Question

Is the following argument correct: A double six in a single turn in game B is 1/6 as likely as rolling a six in one turn in game A. But there are 6 times as many turns in game B as game A. Thus the ...
0
votes
1answer
84 views

Fibonacci numeration system

Instead of binary or decimal, the Kingdom of Leutonia uses an unusual system to represent numbers, based on the Fibonacci sequence. The Fibonacci sequence $F_0,F_1,F_2,\dots$ is defined recursively ...
0
votes
2answers
35 views

How do you determine if a relation is transitive?

Suppose I have the relation P such that $$ x P y $$ iff $$ x = y^2 $$ How do I determine whether or not the relation is transitive?
1
vote
1answer
84 views

Finding Big-O with logarithmic functions

Give a big-O estimate for, $$ (nlog(n) +1)^{2} + (log(n) +1)(n^2 +1)$$ my attempt was: separate the function find the dominant values and take the big-O evaluation This is what I got: first ...
1
vote
2answers
88 views

multiplication rule questions - 7 people attending a concert

7 people are attending a concert. (a) In how many different ways can they be seated in a row? (b) Two attendees are Alice and Bob. What is the probability that Alice sits next to Bob? (c) Bob ...
0
votes
1answer
44 views

Write out the Leutonian numbers that represent the first 12 positive integers.

How could I write out the leutonian numbers that represent the first 12 positive integers ? I have no idea how to start.
1
vote
1answer
45 views

Combining Two Gaussian Filters

I am taking a class related to image processing and we were taught about Gaussian Filters that are related to the following Gaussian Function: $$G(u,v) = \frac{1}{2\pi\sigma^2}e^{-\frac{u^2 + ...
1
vote
1answer
52 views

Find the degree of remaining verticies

A simple graph G has 7 vertices and 9 edges. The degrees of some of its vertices are 2, 2, 4, 2. Furthermore, G is known to have an Euler circuit. Find the degrees of the remaining vertices, and draw ...
0
votes
1answer
192 views

How many ways to choose at least one piece of fruit from 9 apples and 6 oranges

I am wondering if someone can explain the reasoning behind the solution my book gives me to the following problem: How many ways are there to pick some pieces of fruit from 9 oranges and 6 apples if ...
1
vote
2answers
56 views

conjecture and prove sequence value using induction

Conjecture and prove $a_n$ for $n\ge 0$. $a_n=\sum_{i=0}^{n-1}{{n-1}\choose {i}}a_ia_{(n-1)-i},n\ge 1; a_0 $ a fixed constant.
1
vote
2answers
2k views

Why does the wording of how many ways can a photographer 6 people from a group of 10 ask for permutations and not combinations?

Note: Please do not post the mathematical notation for binomial coefficient or "n choose m" or anything related to that. The chapter where that is introduced comes much later. Therefore I would not ...
1
vote
1answer
17 views

Would 3 to the n power where n is an element of Z be countably infinite?

I'm just learning about finite, countably infinite, and uncountable sets. My question is, which of the three categories would this fall into: {3^n|n Ο΅ Z} I first thought that it would uncountable, ...
0
votes
2answers
42 views

One-to-one correspondence of a set within a set

I need to find a one-to-one correspondence between each of the following pairs of sets: $\{x, y, \{a, b, c\}\}$ and $\{14, -3, t\}$ $2\mathbb Z$ and $17 \mathbb Z$ For problem a, I have no idea if ...
1
vote
1answer
62 views

I am learning coding theory in discrete mathematics, can someone illustrate an example of an $alphabet$, code and codeword please?

I have that the following definitions; An $alphabet$ $\sum$ is a set of symbols. A code $y$ over $\sum$ is a collection of sequences of symbols. The members of $y$ are called codewords. Could ...
0
votes
2answers
30 views

Show that two consistent systems are equivalent to each other [duplicate]

$A: n \times n$, $B: n \times m$ and $A$ is invertible. Show that "$\forall \vec{b} \in \mathbb{R}^n, B \vec{x} = \vec{b}$ is consistent" is equivalent to "$\forall \vec{b} \in ...
3
votes
4answers
532 views

Have I negated the statement “for every prime number $p$, $p+7$ is composite” correctly?

This is the original statement: For every prime number $p$, $p+7$ is composite. This is my negation: There exists a prime number $p$, where $p+7$ is prime. Have I negated this correctly?
0
votes
0answers
24 views

difference equations/inequalities in two variables without constant coefficients

I have a linear inhomogeneous difference inequality with variable coefficients. I was wondering if there are any general methods available for solving it. The case where the inequality is replaced by ...
5
votes
2answers
826 views

How to prove a function is not onto?

Let $f : Z\to Z$ be the function defined by $f(x) = 3x + 1$. Prove that $f $ is not onto, using a proof by contradiction. (Choose an integer $n$, and then prove ($\forall m \in Z$)($f(m) β‰  n$) by ...
1
vote
1answer
42 views

Steps to determine if a relation of a set is reflexive,symmetric or transitive?

I am having problem understanding these concepts. For example, let $A = \{2,3,4,5,6,7,8\}$. The definition I found says that $x R y \iff 3 | (x-y)$. How do I know if the relation $R$ on $A$ is ...
2
votes
3answers
39 views

Find $\sum{(-1)^22n }$ from $n=0$ to $n=28$

Find $\sum{(-1)^22n }$ from $n=0$ to $n=28$ I can't find a formula for alternation series
1
vote
2answers
112 views

Using logical Properties to prove a tautology

So I have to prove this as a tautology. I've been stuck on this forever and am not sure where to go. I experimented and got this far, and looking for some pointers on where to take it next. (p β†’ q) ...
1
vote
2answers
46 views

Order of parameters in quantified predicates

I'm studying up for my midterm in Discrete Math and I've been looking at sample questions and their solutions. There is one I don't really understand and I was hoping someone could help me out. ...
7
votes
0answers
70 views

For what numbers is $a_{b}= b_{a}$? (Reference?)

A student recently asked me about solutions to the equation $$a_{b} = b_{a},$$ where the subscript notation $a_{b}$ denotes interpreting the digits of $a$ in base $b$. It turns out there are tons of ...
0
votes
1answer
70 views

proof by induction for summation

This is not a duplicate. I know my conjecture is right, just need to prove it, using induction(not Gauss Method). Conjecture formula from following equations, and prove conjecture: ...
0
votes
2answers
22 views

discrete math, problem on combinations

there are 6 undercase letters in a password, how many passwords are there if you have to use at least one 'a'?? I have calculated the total number of passwords which is 26^6 and I have calculated the ...
0
votes
3answers
60 views

How to find the integral of $(1-|\tau|)\cos(\omega\tau)e^{-j\omega\tau}$

I have a function that need calculate the integral. Could you help me to find it. Thank you so much $$f(\omega)=\int_{-1}^1(1-|\tau|)\cos(\omega\tau)e^{-j\omega\tau}d\tau$$ where $\omega$ is constant. ...
0
votes
1answer
111 views

# of ways to place books on shelf

This is a question about the the # of ways I can place the books on shelves. I have to place a book on n number of shelves with m number of books; m >= n >= 1. But I have to have atleast 1 book on ...
-4
votes
3answers
75 views

Is it correct to conclude $x\notin A \implies x\in\bar{A}$?

Am I allowed to do this: $$ x\notin A \implies x\in\bar{A} $$ ($\bar A$ is the set complement) in the context of this proof?
1
vote
2answers
59 views

How do you solve these recurrence relations for a closed form?

I'm not sure what methods are used to solve recurrence relations for a big-$O$ notation. Thinking about the problem conceptually doesn't really help me, but I feel like I could use some form of ...
0
votes
4answers
65 views

Why is my reasoning wrong in determining how many functions there are from set A to set B?

I am trying to count how many functions there are from a set $A$ to a set $B$. The answer to this (and many textbook explanations) are readily available and accessible; I am not looking for the ...
0
votes
1answer
40 views

How do you typically prove recurrence relations?

The median-of-medians algorithm gives a recurrence relation $T(n) = T(n/5)+T(7n/10)+n = O(n)$. If the subgroup was changed to a size 3 or 7, how would this effect the recurrence relation? I came to ...
0
votes
1answer
35 views

How do I simplify this Laws Of Logic question?

So far I have done most of the work, but I have hit a wall.... I jist cant seem to get past these few steps to get the final answer. Can someone help me figure out the last few steps. I have spent ...