Tagged Questions

15 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
35 views

Prove or disprove for any real number

Prove or disprove for any real number $x^2 < x$ , considering $0.5^2 = 0.25, 0.25 < 0.5$
70 views

Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N ex ...
44 views

77 views

Is proving both sides of iff necessary?

I have always been taught to prove both ways of an "if and only if" statement in a formal proof, but if the opposite way is very similar to the proof of the first way. Can you just leave a note and ...
49 views

Help with a proof in discrete math.

I have been trying to figure out this problems to no avail. Problem $1$: Show that there are infinitely many natural numbers $x,y,z$ such that $$\frac{1}{x} + \frac{1}{y} = \frac{1}{z}.$$ Thank ...
76 views

Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
39 views

Strong Induction - Understanding the lateral conditions.

I dont want the proof of this statement unless it is necessary for my questions, I just want some clarification. If cr = 1 would cr-1 = 0? How is cj 1 or 0? I understand cj is an arbitrarily ...
313 views

Prove that between every two rational numbers a/b and c/d that there is a rational number and there are an infinite number of rational numbers [duplicate]

So the full problem is Prove that between every two rational numbers $a/b$ and $c/d$ that: There is a rational number There are an infinite number of rational numbers I am having ...
42 views

Suppose x and y are coprime integers and z is a natural number. Prove that If xy is a zth power then x and y are both zth powers.

I'm supposed to use a prime factorization somewhere, and that the fundamental theorem of arithmetic is to be applied as well.
49 views

Proof concerning Latin squares

I'm asked to solve this problem : Let $R$ be an $r\times c$ partial Latin rectangle using the numbers $[n]= \{1,2,...,n\}$. Suppose that $r < n$ and $c < n$, and let $N(i)$ be the number of ...
53 views

Let x and y be integers, let x and y be greater than 0. Prove that the gcd (x/gcd(x,y) , y/gcd(x,y) = 1

Very confusing, not really sure how I'm supposed to deduce what $\gcd (x,y)$ is and how $$\gcd \left(\frac{x}{\gcd(x,y)} , \frac{y}{\gcd(x,y)}\right)$$ can be $1$?
72 views

Suppose $X$ and $Y$ are greater than $0$. Show that $\gcd(X,Y)$ is $1$ iff $\gcd(X^m,Y^m)= 1$

Please help with the above I have no idea whats going on. An explanation would be nice.
36 views

Greatest Common Divisor Proof

If $d = \gcd(a,n)$, must $\dfrac ad$ and $n$ be relatively prime? Prove or disprove. Do I show that they need to be relatively prime and then the inverse that they do not need to be relatively ...
89 views

Show Pascal triangle properties

I need to prove two pascal triangle properties: 1) $\sum_{k=0}^{n}\binom{p+k}{k}=\binom{p+n+1}{n}$ 2) $\sum_{k=0}^{n}\binom{k}{p}=\binom{n+1}{p+1}$ I need some advice on how to approach to this ...
24 views

Prove If hcf(a,b)|c then then ax+by=c has an integer solution. Where a and b are non-zero integers.

I'm not sure whether to use multiple cases for this particular question (i.e. odd*odd with hcf=1 and odd*even with hcf=1 have integer solutions for x and y).
135 views

Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
40 views

Transitive closure of binary relation with proof of equivalence

On the set X = {1,2,3,4,5,6,7,8,9}, there is binary relation Q = {(1,9),(2,5),(3,7),(4,1),(5,8),(6,2),(7,3),(8,6),(9,4)}. Make a transitive closure T of the relation Q. Decide and prove whether the ...
34 views

Why does this proof need another case?

A psuedograph (with at least two vertices) is Eulerian if and only if it is connected and every evertex is even. Proof: (-->) understood so let's move on. (<--) For the converse, suppose that G is ...
126 views

Prove if a≡c (mod n) and b≡d (mod n) then ab≡cd (mod n)

Prove if a≡c (mod n) and b≡d (mod n) then ab≡cd (mod n). I tried to (a-c)(b-d)=ab-ad-cb+cd, but it seem doesn't work.
60 views

What is the proof that $\sum \limits_{v \in V} deg(v) = 2|E|$?

My textbook gives $\sum \limits_{v \in V} deg(v) = 2|E|$ and has the proof If an edge is not a loop it gets counted twice b/c it's incident with 2 different vertices. If an edge is a loop, by ...
29 views

Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property

Let $X=\{1,2,\dots,10\}$ define the relation $R$ on $X$ by: for all $a,b\in X$, $a\mathrel{R}b \iff ab$ is even. 1) Find the number of subsets $S$ of $X$ (of any size) that satisfy the ...
64 views

prove that one of the digits 1,2…9 occurs infinitely often in the decimal expansion of pi

prove that one of the digits 1,2...9 occurs infinitely often in the decimal expansion of pi. you may use without proof the fact that pi is irrational. It is recommended using proof by contradiction. ...
24 views

Advice for proving with induction scenarios with multiple chances for using the hypothesis.

I have done many, many questions about solving induction exercises. I managed to grasp a basic strategy: write all the information, take the statement you want to prove, try to apply the hypothesis ...
49 views

Defining an Infinite Matrix

Hey I am getting ready for my final exam and I'm having trouble figuring out this practice question: Let X be a random variable that takes values in {0,1,2,3,...}. It is known that: E(X) = ...
31 views

Proving by induction inequalities that lack the variable on the right side.

Doing proof by induction exercises with inequalities, I got stuck on one that is a bit different from the others. There is no $n$ term on the rightmost part of the inequality: Prove that the ...
82 views

Proving by induction that $1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}\le\frac{n}{2}+1$ holds for all $n \ge 1$

While looking at some examples of proof by induction related to inequalities, I had this one that I didn't quite get: Prove by induction that the following holds for all $n \ge 1$: ...
39 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
45 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
33 views

Strong induction proof with polygon

How can we show that if a simple polygon with at least four sides is triangu-lated, then at least two of the triangles in the triangulation have two sides that border the exterior of the polygon using ...
62 views

Proof related with mathematical induction

I tried to prove this claim using mathematical induction. $a^2 + 15a + 5 ≤ 21 a^2$ $\;\; ∀a∈\mathbb Z^+$ The way is as the following: Basis: for a = 1 is true since 21 = 21 Inductive step: If ...
57 views

How to prove that if n and k are integers with 1 ≤ k ≤ n, then k*(n C k)=n(n−1 C k−1) combinatorally?

I am having with combinatorial proofs. My professor says to come up with a scenario so that we can connect both sides by double counting but I am clueless.
31 views

Proof for the length of the shortest 4-connected path and 8-connected path on a chessboard

I have a chessboard with a square marked with A as in the following figure: $$\begin{array}{|c|c|c|} \hline 8&1&2\\ \hline 7&A&3\\ \hline 6&5&4\\ \hline \end{array}$$ The ...
44 views

Convergence of formal power series substitution

Prove that the substitution of formal power series $F(G(x))=\sum_{k\geq0}f_k \frac{G(x)^k}{n!}$ converges for every $F$ if and only if $G(0)=0$
58 views

Question about the infinite products of formal power series

I need a proof for this: Let $(F_j)_{j\ge 0}$ be a sequence of formal power series. The infinite product $\prod_{j\geq0}(1+F_j(x))$, where $F_j(0)=0$, converges if and only if ...
213 views

Formal power series, the Chain Rule and the Product Rule.

Definitons Let $$\mathbb{C}[[x]] := \left\{ \sum_{n\geq 0} a_n x^n : a_n \in \mathbb{C} \right\}$$ be the set of formal power series of $x$. Exercise i) If $F_1(x)$ and $F_2(x)$ are power series ...
69 views

Deterministic Finite Automata with finite strings

How could I prove that every language with a finite number of strings is the language of some DFA?
75 views

Difficult Discrete/Probability Problem

Here's the question: For a function $f:[n]\rightarrow[n]$, where $n$ is the set $\{1,2,3,\ldots,n\}$, define the inverse complexity, $ic(f)$ as the number of ordered pairs $\langle i,j \rangle$ ...
44 views

Variance of the Random Variable $|im(f)|$ where $f:[n] \rightarrow [n]$

Here's a question: Let $f$ be picked randomly from the set of all functions from $[n]$ to $[n]$, where $[n]$ is the set $\{1,2,3,\ldots,n\}$. Give a closed-form expression for the variance of the ...
Proving $n! < n^n$
I have to prove $n! < n^n$ for positive integers greater than 1, but with a little twist. I have to show $P(n-1)$ holds. For the left, I know $(n-1)! = \frac{n!}{n}$ and I'm stuck from there ...