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

1
vote
1answer
21 views

Question about problem 53 in Problem Solving and Selected Topics in Number Theory

I solved problem 53 in Problem-solving and selected topics in Number Theory. The problem was: Find the sum of all positive integers that are less than 10,000 and whose square divided by 17 leaves ...
0
votes
0answers
21 views

discrete math cryptography

An affine cipher is encryption using a simple mathematical function. Consider the affine cipher $c = ax+b \pmod{26}$ where $x$ is the plaintext, the function applied to each letter of the plaintext ...
0
votes
1answer
26 views

Prove that every integer from 1 to p – 1 occurs exactly once among these residues.

Let $p$ be a prime and $1 \leq a \leq p-1$. Consider the numbers $a, 2a, 3a, \cdots, (p-1)a$. Divide each of them by $p$, to get residues $r_1,r_2, \cdots,r_{p-1}$. Prove that every integer from $1$ ...
1
vote
2answers
28 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
0
votes
1answer
23 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem: Each of the K knights from the round table needs to choose a card which is marked with a number from 1 to N, N >= K. The cards all have different number. ...
0
votes
1answer
41 views

Prove that if p is a prime, a and b are integers

(a) if p | ab, then either p | a or p | b or both. (b) if a | b, p | b, but a is not divisable by p , then p | b/a. I have no problem with the part a I solved that but need some serious help on ...
0
votes
0answers
13 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...
0
votes
1answer
25 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer n>=2 is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= p(n) for n=1 or any arbitary ...
1
vote
2answers
13 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ ...
1
vote
6answers
77 views

The function $G: x \mapsto 2^{x^2}$ maps $\mathbb{R}$ onto $\{ x \in \mathbb{R} : x \geq 1 \}$

Let $X = \mathbb{R}$ and $Y = \{x \in \mathbb{R} :x ≥ 1\}$, and define $G : X → Y$ by $$G(x) = e^{x^2}.$$ Prove that $G$ is onto. Is this going along the right path and if so how do get the ...
0
votes
0answers
14 views

dimension of vector space $\frac{\langle e_{ab_1\ldots b_p}\rangle}{\langle \sum_{1\leq i\leq p}e_{ab_1\ldots \widehat{b_i}\ldots b_pc}\rangle}$

Let $p$ be a prime and $n\!\in\!\mathbb{N}$. What is the dimension of the $\mathbb{Z}_p$-module $$V_{p,n}=\frac{\langle e_{ab_1\ldots b_p};\: 1\leq a<b_1<\ldots<b_p\leq n\rangle}{\langle ...
0
votes
1answer
37 views

Find all real numbers $x$ such that: $\lfloor 7x\rfloor = 7$

I'm not quite sure how to approach this. Does $x$ have to be very small for it to work?
0
votes
1answer
28 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
3answers
20 views

Let $ a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. use the result of par t $ a)$ to solve the Diophantine equation $ a+b=ab$

Not sure if I did part a right, not sure how to complete part $b)$ $a)$ Let $a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. Proof by contradiction suppose $\text{gcd}(n, n-1) = p > ...
-2
votes
1answer
20 views

Probability: How much days we need to play a game win

Suppose the probability of win a lotery game is : $1/1000$ If a person play the lotery every day with the same combination, how much time he need to wait to win the lotery? Im thinking to use a ...
0
votes
5answers
36 views

Give the number of solutions of $x+y+z = 30$, for $4 \leq x \leq 14$, $3 \leq y \leq 17$, $10 \leq z \leq 25$.

How would I find the number of solutions with both upper and lower bounds? Can anyone give a step by step way to solve this problem? This is question is in preparation for my discrete math final, so ...
7
votes
6answers
81 views

Solve $\lfloor \sqrt x \rfloor = \lfloor x/2 \rfloor$ for real $x$

I'm trying to solve $$\lfloor \sqrt x \rfloor = \left\lfloor \frac{x}{2} \right\rfloor$$ for real $x$. Obviously this can't be true for any negative reals, since the root isn't defined for such. My ...
0
votes
0answers
17 views

Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

On the last page of the Josephus problem where things get really general, we're shown the pretty slick radix changing recurrence & solution 1.17 & 1.18 f(j) = aj, for 1 <= j <= d; ...
-3
votes
1answer
30 views

Use mathematical induction to show that [on hold]

Use mathematical induction to show that $3^n + 7^n − 2$ is divisible by $8$ for all $n\ge 1$. [Hint: $7^n + 1$ is divisible by $2$.]
1
vote
1answer
23 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
3
votes
2answers
25 views

Proof by induction for $ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $

Can someone show me an induction for $$ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $$? My problem is doing that induction with $M$, I am not sure how to proceed to get the right side of ...
1
vote
3answers
49 views

If $A\times B \subset A\times C$, does it follow that $B \subset C$?

On a study guide I have the following question: If $A\times B \subset A \times C$, does it follow that $B \subset C$? Prove or disprove. To me, I think the answer is yes, but I have no idea of ...
0
votes
2answers
19 views

Equivalence relation and equivalence classes

Each bead on a bracelet with three beads is either red, white, or blue. Define the relation R between bracelets as: (B1, B2), where B1 and B2 are bracelets, belongs to R if and only if B2 can be ...
0
votes
1answer
35 views

Prove a functions is injective

Prove the function $f:\mathbb{N} \to\mathbb{N}$defined by $f(x)=2^x$ for all $x$ in $\mathbb{N}$ is one to one. Is my proof correct and if not what errors are there. For all $x_1,x_2$ $\in$$N$, ...
0
votes
2answers
30 views

Matrix rings and ideals

How would one go about checking if a given 2 x 2 matrix is an ideal. I am unclear as to what an ideal is and would like to know the steps in order to make the verification. Also, if it helps, I had ...
0
votes
1answer
16 views

Discrete Mathemetics - Hamilton Path

G is a simple connectivity graph. we added to G few edges (without adding any vertex), and we received graph H, which is also an simple graph. which one are true: ...
0
votes
2answers
17 views

GCD proof using fundamental theorem of arithmetic

prove: $\gcd(m,n)=1$ if and only if $\gcd(m^i,n^r)=1$ I believe you need to do something with fundamental theorem of arithmetic to prove one of the sides. Not quite sure though. Help is appreciated. ...
-2
votes
1answer
33 views

Combinatorial Argument Proof

Prove: $c(40,5) = c(17,5) + c(17,4) + c(23,1) +...+ c(23,5)$ where c is the binomial coefficient. Can I use a combinatorial argument to prove?
0
votes
2answers
41 views

Proof using Induction

Give the induction proof of: $$ 1.2 + 2.3 + k(k+1) = \frac{k(k+1)(k+2)}{3} $$ Is this proof even possible? Not sure how to do.
0
votes
1answer
20 views

How to verify an algebraic structure is a ring

I have a problem which ask me to verify that to structures are rings. However, I'm unsure of how exactly to check each property. I believe that the first is closed but not sure how to check the ...
-2
votes
1answer
27 views

a formal logic proposition about real numbers

I have the following informal statement about real numbers: Every real number except zero has a multiplicative inverse. Can this be expressed as: $$ \forall x \exists y(x\neq 0 \implies xy=1) ...
0
votes
1answer
10 views

Clarification on Eulirian cycle proof

I have trouble in understanding this proof can some one clarify the following elements: (1)Why does it follow that if T has maximum length, then $v_0=v_k$?(2)What does E represent?(3)What does E(T) ...
2
votes
2answers
80 views

A Proof for Prime Numbers

Show that among k-digit numbers, one in about every 2.3k is a prime. How can we prove this question? Thanks.
0
votes
0answers
16 views

Minimal “basis” in $n$ dimensional unit cube

Let's $$ B^n=\{\bar\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)|\alpha_i\in \{0,1\}\};~~~~n=1,2,\ldots $$ and let's $$ C\subseteq B^n, $$ $$ S(C)=\{\bar\alpha\oplus\bar\beta\ | \bar\alpha,\bar\beta\in ...
1
vote
0answers
20 views

A second order problem on recurrence relation equals 3^n

I had this Recurrence Relation problem: $a_{n+2} + a_{n+1} - 12a_n = 0$ And I solved in a form like this $a_n = A(r_1)^n + B(r_2)^n$ $r^{n+2} + r^{n+1} - 12r^n = 0$ ...
0
votes
0answers
18 views
0
votes
2answers
32 views

Define a sequence of integers $H(n)$ by $H(0) = 1$, $H(1) = 3$ and $H(n+1) = H(n) + H(n-1)$?

Then show that $H(n)$ can be expressed in the form $a\cdot(\psi(1))^n + b\cdot(\psi(2))^n$ and that $\psi(1)$ and $\psi(2)$ are the same numbers that occur in the proof of the Fibonacci numbers. I'm ...
0
votes
1answer
28 views

Let A and B be countable sets. Is there any function f such that a certain condition holds for an uncountable number of functions g?

Let $A$ and $B$ be countable infinite sets. Is there any function $f:A\rightarrow B$ such that the number of functions $g:B\rightarrow A$ with property that $g\circ f=\mathrm{id}$ but $f\circ ...
0
votes
2answers
28 views

Combinatorics (discrete math course) help

problem 1: you have 4 balls with different weights and 6 drawers stacked on top of each other. how many ways are there to organize the balls such that the top drawer will have exactly 1 ball and the ...
1
vote
3answers
41 views

Evaluate $\sum_{k=400}^{2000} \frac {2^{3-4k}} {8^{2k+3}}$

Evaluate $$\sum_{k=400}^{2000} \frac {2^{3-4k}} {8^{2k+3}}$$ So far, I was able to get to $$\frac{1}{64}\sum_{k=400}^{2000} \frac {1} {8^{2k}\cdot2^{4k}}$$ And then I'm completely stuck.
0
votes
2answers
20 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
1
vote
2answers
24 views

Obtain and prove the rule for divisibility by $ 3$? [duplicate]

I was very confused by this problem, I don't even know what it is asking. Any help would be great :) thanks in advance.
0
votes
1answer
12 views

Justify each step in the proof sequence

$[A \rightarrow ( B \lor C) ] \land B' \land C' \rightarrow A'$ I know how to read the proof sequence, but I don't know what it means to "justify" each step? Does this mean to just state what each ...
3
votes
2answers
53 views

Show that it is the solution of the recurrence

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$ I used induction to show that. I have ...
2
votes
2answers
36 views

Convert form English to logical symbols.

I have a logical argument in English which says. All Humans are Mortal. Zeus is not Mortal. therefore Zeus is not Human. And I tried to convert it from English to logic. and did this h = is ...
3
votes
2answers
38 views

GCD Direct Proof

I need to show that if $a,b,c$ are ints such that $\gcd(a,b) = 1$ and $c|(a+b)$, then $\gcd(c,a) = \gcd(c,b) = 1$ I want to try and prove this directly because I think it will be more straightforward ...
1
vote
1answer
21 views

Proving n is not divisble by m using Division Algorithm

When $n$ and $m$ are integers, how could I write a statement equivalent to the statement "$n$ is not divisible by $m$" using ideas from the Division Algorithm?
2
votes
0answers
28 views

Solve the recurrence $T(n)=aT(n-1)+bn$

I have to solve the following recurrence, given $T(1)=1$, $$T(n)=aT(n-1)+bn$$ I have done the following: $$T(n)=aT(n-1)+bn \\ =a^2T(n-2)+ab(n-1)+bn \\ =a^3T(n-3)+a^2b(n-2)+ab(n-1)+bn \\ = \dots \\ ...
0
votes
2answers
16 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
2
votes
1answer
31 views

Preorder traversal, inorder traversal, postorder traversal

a) preorder traversal b) inorder traversal c) postorder traversal Ok, a) r,j,h,g,e,d,b,a,c,f,i,k,m,p,s,n,q,t,v,w,u b) a,b,d,c,e,g,f,h,j,i,r,s,p,m,k,n,v,t,w,q,u c) ...