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

abstract machine, what language does M accecpt?

What language does M accept? 1: {a}3 ∪ {b}3 ∪ {λ} 2: {a}3 ∪ {b}3 3: {a, b}3 ∪ {λ} 4: {a, b}3 ∪ {λ} I'm not completely sure just yet which one would work. I would appreciate it if ...
1
vote
3answers
55 views

Hard Mathematical Induction [duplicate]

I have a mathematical induction question and I know what I need to do just not how to do it. The question is: Prove the equality of: $$(1 + 2 + . . . + n)^2 = 1^3 + 2^3 . . . + n^3$$ Base ...
0
votes
0answers
22 views

Bounding a discrete function

If there is a discrete-time function $u(t)$, where $u(T)=u(0)+\sum_{t=0}^T G(u(t))$, is it possible to prove that $u(t)$ remains bounded for a specific class of $G$ functions? Such as $G\in L^1$ or ...
1
vote
0answers
18 views

Solving a recurrence with a term $T(\frac n 2 + 2)$

I'm stuck trying to solve the following recurrence: $$\begin{align*} T(n) &= 4T(\frac n 2 + 2) + n : n > 8\\ T(n) &= 1 : n \leq 8 \end{align*}$$ In particular, I'm not sure how to deal ...
0
votes
2answers
27 views

I am kind of confused on how to solve this question. Can anyone help please

If we let $S$ be the set that is defined by the following two rules: 1 is an element of the set $s$ If $s$ is an element of the set $s$, then x+$2 \sqrt{x}+1$ is also an element of the set $s$ how ...
0
votes
2answers
63 views

How do i prove these type of questions? I am Really stuck.

How do I solve this textbook question: If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$ How do I determine $A_1$, $A_2$, ...
1
vote
1answer
46 views

How can I solve this recursion question, I am really stuck. [duplicate]

I am doing a couple of exercise questions, How do I show that if we let $n \geq 1$ be an integer, and if we consider $n$ people $P_1$,$P_2$,...,$P_n$. If we let $A_n$ be the number of ways these $n$ ...
1
vote
0answers
37 views

proving Fibonacci numbers using mathematical Induction?

Can anyone confirm whether my answer is correct, please. Let suppose we have the following fibonacci numbers as shown: $f(0) = 0, f(1) = 1$, and $f(n) = f(n-1) + f(n-2)$ for $n \geq 2$. Prove that ...
1
vote
3answers
40 views

Prove that $1 + 4 + 9 … + n^2 = (n/6)(n+1)(2n+1)$

I know that it is true but not sure how to write the proof for: $1 + 4 + 9 ... + n^2 = (n/6)(n+1)(2n+1)$. I need help to guide me in the right direction. Thanks in advance. edit: Okay at n=k I have ...
0
votes
1answer
41 views

prove conjunction of consecutive implications

$n\ge 2,p_1,p_2,p_3,...,p_n,p_{n+1}$ are statements. Prove $(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\wedge ...\wedge (p_n\rightarrow p_{n+1})$ $\Rightarrow (p_1\wedge p_2\wedge ...
1
vote
1answer
41 views

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $.

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $. I know that $f(x)$ is $\theta (g(x)) $ if it is both $ O(g(x)) $ and $\Omega (g(x))$ when $ x > n$ I reasoned that $f(x)$ is ...
2
votes
5answers
84 views

Prove that $\left(\sum_{k=1}^{n}k\right)^2=\sum_{k=1}^{n}k^3$ holds true for $n ≥ 1$

I've been trying to figure out this proof for way too long now, I'm just not sure where to begin for the inductive step. Any guidance would be greatly appreciated.
0
votes
1answer
32 views

Interpreting logic word problems

Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the ...
0
votes
1answer
72 views

Basic set theory - discrete mathematics

Please help me with this question! I've always thought that if xy = z, then x or y must be a factor of z and so doesn't that mean all values of n are possible where at least one of the numbers is a ...
1
vote
1answer
54 views

Showing a set is a subset of another set

I need to show that $(A \cup B) \subseteq (A \cup B \cup C)$ My Work So Far: What I really need to show is that $x \in (A \cup B)$ implies $x \in (A \cup B \cup C)$ So I translated my sets into ...
1
vote
1answer
34 views

Determine whether tautology or contradiction.

(p → (q → r)) → ((p ∧ q) → r) ⇐⇒ ¬ (¬p ∨ (¬q ∨ r)) ∨ (¬(p ∧ q) ∨ r) expression for implications ⇐⇒ (p ∧ q ∧ ¬r) ∨ (¬p ∨ ¬q ∨ r) DeMorgan’s law ⇐⇒ (p ∧ q ∧ ¬r)∨ ≠ ((p ∧ q ∧ ¬r)) DeMorgan’s ...
1
vote
2answers
19 views

Describe the preimage of the set

I've been stumped on this problem for a while now, unable to find many resources to help me understand how to describe a preimage of a set given a function like this one. Let $f$: $\mathbb Z \to ...
0
votes
3answers
120 views

Truth Table problems

The problem: You are walking in a labyrinth, which contains at its center a vast treasure. Suddenly, you find yourself in front of three possible paths: a gold path to your left, a marble ...
0
votes
1answer
57 views

Recursion: Dividing n people into groups of 1 or 2

Let $n \ge 1 $be an integer and consider $n$ people $P_1, P_2, . . . , P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group consists of either one ...
5
votes
4answers
617 views

Sum of cubes proof

Prove that for any natural number n the following equality holds: $$ (1+2+ \ldots + n)^2 = 1^3 + 2^3 + \ldots + n^3 $$ I think it has something to do with induction?
1
vote
4answers
181 views

Prove that if both $ab$ and $a + b$ are even, then both $ a$ and $b$ are even.

Let $a$ and $b$ be integers. Prove that if both $ab$ and $a + b$ are even then both $a$ and $b$ are even. I've seen some solutions but they're not worded in a very simple way. Any help would ...
0
votes
3answers
34 views

Ways of spending money combinatorial problem

Suppose person X has $12$ dollars.In each of the first 5 days he buys one of the following items. 1.Item A for $1 2.Item B for $2 3.Item C for $3. In how many ways can he spend the money ...
1
vote
2answers
93 views

Permutaion and Combination Problems

Hey folks I'm having some issues with permutation and combination problems. 1) Make a 3 digit even number without repeated digits, using 0, 4, 5 , 6, 7. Also the first digit cannot be 0. I ...
1
vote
2answers
45 views

Showing Discrete Sum Equality

The questions asks to show that $\sum\limits_{k=0}^n (-1)^{k}{n \choose k}(n-k)^{r} = \begin{cases}0 & r=1,2,3,...,n-1 \\ n! & r = n \end{cases}$ Any help would be appreciated. I'm ...
1
vote
2answers
60 views

Identifying laws in a discrete math example

I'm studying for my upcoming discrete math test and I'm having trouble understanding some equivalences I found in a book on the subject. I guess I'm not really familiar with these rules and I would ...
4
votes
8answers
77 views

Null Sets $\{\{\emptyset\}\} \subset\{\emptyset, \{\emptyset\}\}$

Regarding null sets, I'm wondering if anyone can explain this $\{\{\emptyset\}\} \subset \{\emptyset, \{\emptyset\}\}$ I don't understand how the left set is a proper set of the right set. In ...
0
votes
0answers
27 views

Prove using Induction : Recursion

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
1
vote
6answers
119 views

What is a “formal definition” of a set?

I'm to find a formal definition of a certain set, but I'm unsure what it means by "formal definition" (in relation to Discrete Maths) A quick google search didn't seem to help me much. Can anyone ...
0
votes
2answers
123 views

How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$? My questions is, can I choose an $n$ randomly? For example, let's say ...
0
votes
1answer
29 views

Combo: Unambiguous expression - String

I am stuck on finding an unambiguous express so that it can produce all the strings in the given set, for the set of binary strings where for each block of zero's which are of length minimum 3 must be ...
0
votes
3answers
92 views

Show that if taken 14 number from 1 to 25 at least one of them is multiple of another

Let $S = \{1, 2, \dots, 24, 25\}$. Show that for any subset $R \subset S$ with $|R| = 14$, there are $a,b \in R$ such that $a|b$. I know that it is a pigeonhole problem but i don't know how to solve ...
0
votes
0answers
15 views

solving a set of equations for discrete probability distribution

Could you please help me to solve this set of equations analytically to find p_i s? $$p_i=\frac{N}{N-1}\frac{1}{i-1}[i p_i^2-\sum_{k=1}^ip_k^2]$$ for $$i=2,...,N$$ and $$\sum_{i=1}^Np_i=1$$
0
votes
1answer
26 views

Largest and least amount of connected components of graph with conditions

A graph G without loops and parallel edges has the following properties:$$|V|=30$$$$|E|=30$$ It also has a cycle of length 10. What is the largest and the least amount of connected components in the ...
0
votes
2answers
68 views

Recursion: putting people into groups of 1 or 2

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
1
vote
1answer
53 views
+100

The no. of ways dividing a polygon with $n+1$ sides into triangular regions…

Please if any one can help me explaining this concept,as I have my exam tomorrow and I can't proceed further due to this.... Let $h(n)$ denote the no. of ways dividing a convex polygon region ...
0
votes
0answers
22 views

Prove that the set is countable [duplicate]

Question: We call a real number $x$ $algebraic$ if $x$ is the root of a polynomial equation $c_{0}+c_{1}x+...+ c_{n}x^{n}$ where all $c_{i}$'s are integers. For example $\pm \sqrt{3}$ are algebraic ...
0
votes
1answer
44 views

riddles and compound proposition

I've been learning about propositions and truth tables recently and been given examples like "If it is raining I will take my umbrella." P=it is raining Q=i take my umbrella. It's very easy to ...
0
votes
2answers
178 views

Discrete Mathematics Sets. ∀x∀y(xy ∈ nN) =⇒ (x ∈ nN ∨ y ∈ nN).

Let N = {0,1,2,3,...} be the set of natural numbers. For a number n let nN denote the set of all multiples of n, i.e. nN = {nx : x ∈ N}. For each integer n consider the proposition p(n) given by ...
0
votes
0answers
23 views

Determine the Equivalence Class

Let $N$ be a set of all natural numbers. $R$ is a relation on $N$ where $((a,b)(c,d))$ is the element of $R$ if and only if $ad=bc$. Determine the equivalence class of $R$. Is it be written in the ...
2
votes
3answers
49 views

if $2$ and $3$ does not divide n, then prove $n^2 = 12q + 1$

I need a proof for this statement: if $2$ does not divide $n$ and $3$ does not divide $n$, then $n^2 = 12q + 1$. What I have so far: i) if $2$ does not divide $n$, then $n$ is not even.
0
votes
4answers
47 views

Method of Proof (Computer Science) [duplicate]

Prove that $1+r+r^{2}+...+r^{n-1}=\frac{r^{n}-1}{r-1}$, $r$ a positive integer, $r \neq 1$
0
votes
1answer
25 views

How to get the negation of logic statement

I though getting negation is to get the opposite. Is there an algorithm to do this: Find the symbolic form and the negation of the statement If he eats, he will walk home My take would be: If he ...
0
votes
2answers
25 views

True conditonal statement with false converse [duplicate]

Is it possible to have a true conditional statement with a false converse? If there is does anyone have an example of one? or why doesn't one exist?
1
vote
3answers
31 views

Showing that a sequence $a_n$ is a solution of the recurrence relation

I'm having some trouble with showing that a sequence $a_n$ is a solution to the recurrence relation $a_n = -3a_{n-1} + 4a_{n-2}$. (See image below). The sequence $a_n$ that is given $= (-4)^n$ . I'm ...
1
vote
1answer
59 views

Mathematical induction base case is not initial

Prove by induction that $$1+2+3+\cdots+n= \frac{n(n+1)}{2}$$ for all integers greater than or equal to $2$ How can you solve this if the base case is not $1$? I thought it might be a strong ...
0
votes
1answer
40 views

Basic principles: independent choice, counting functions and subsets

Calculate the number of passwords of length 8 using letters A..Z such that adjacent letters are distinct. For example, GJLYNDBF is a good password, while GJLYYDBF is not good (two adjacent Y's).
0
votes
1answer
80 views

Pascal's Triangle

My question is the following; Q: Prove that if we move straight down in Pascal’s Triangle (visiting every other row), then the numbers we see are increasing. Found an answer but that doesn't count ...
1
vote
1answer
21 views

Strictly convex sequence

A sequence of numbers $A=(a_1, a_2, \dots, a_n)$ is called strictly convex, if there is a $k$, with $1 \leq k \leq n$ so that for all $1 \leq i \leq k-1$ we have $a_i>a_{i+1}$ and for all $k \leq i ...
2
votes
2answers
32 views

How to prove the following $\Theta$notation

If the following function is given: $f(n)=n^2+ n \ln(n)+1$. How do you prove the $\Theta$ notation? I assume that is must be $\Theta$($n^2$). But I'm not sure how to solve it.
0
votes
1answer
59 views

How many combinations can I make?

let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two ...