Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged proof
37
votes
5
answers
241
GATE CSE 1989 | Question: 4-i
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
makhdoom ghaya
7.0k
views
makhdoom ghaya
asked
Nov 29, 2016
Combinatory
gate1989
descriptive
combinatory
normal
proof
+
–
23
votes
9
answers
242
GATE CSE 1987 | Question: 10e
Show that the conclusion $(r \to q)$ follows from the premises$:p, (p \to q) \vee (p \wedge (r \to q))$
Show that the conclusion $(r \to q)$ follows from the premises$:p, (p \to q) \vee (p \wedge (r \to q))$
makhdoom ghaya
5.3k
views
makhdoom ghaya
asked
Nov 14, 2016
Mathematical Logic
gate1987
mathematical-logic
propositional-logic
proof
descriptive
+
–
15
votes
3
answers
243
GATE CSE 1987 | Question: 9c
Show that the number of odd-degree vertices in a finite graph is even.
Show that the number of odd-degree vertices in a finite graph is even.
makhdoom ghaya
1.9k
views
makhdoom ghaya
asked
Nov 14, 2016
Graph Theory
gate1987
graph-theory
degree-of-graph
descriptive
proof
+
–
1
votes
0
answers
244
ISI2011-PCB-A-3a
Consider an $m \times n$ integer lattice. A path from $(0, 0)$ to $(m, n)$ can use steps of $(1, 0)$, $(0, 1)$ or diagonal steps $(1, 1)$. Let $D_{m,n}$ be the number of such distinct paths. Prove that $D_{m,n} = \Sigma_k \begin{pmatrix} m \\ k \end{pmatrix} \begin{pmatrix} n+k \\ m \end{pmatrix}$
Consider an $m \times n$ integer lattice. A path from $(0, 0)$ to $(m, n)$ can use steps of $(1, 0)$, $(0, 1)$ or diagonal steps $(1, 1)$. Let $D_{m,n}$ be the number of ...
go_editor
546
views
go_editor
asked
Jun 3, 2016
Combinatory
descriptive
isi2011
combinatory
proof
+
–
2
votes
0
answers
245
ISI2011-PCB-A-1
Let $D = \{d_1, d_2, \dots, d_k\}$ be the set of distinct divisors of a positive integer $n$ ($D$ includes 1 and $n$). Then show that $\Sigma_{i=1}^k \sin^{-1} \sqrt{\log_nd_i}=\frac{\pi}{4} \times k$. hint: $\sin^{−1} x + \sin^{−1} \sqrt{1-x^2} = \frac{\pi}{2}$
Let $D = \{d_1, d_2, \dots, d_k\}$ be the set of distinct divisors of a positive integer $n$ ($D$ includes 1 and $n$). Then show that$\Sigma_{i=1}^k \sin^{-1} \sqrt{\log_...
go_editor
310
views
go_editor
asked
Jun 3, 2016
Geometry
isi2011
descriptive
proof
trigonometry
non-gate
+
–
1
votes
0
answers
246
ISI2014-PCB-A-1a
Let $x=(x_1, x_2, \dots x_n) \in \{0,1\}^n$ By $H(x)$ we mean the number of 1's in $(x_1, x_2, \dots x_n)$. Prove that $H(x) = \frac{1}{2} (n-\Sigma^n_{i=1} (-1)^{x_i})$.
Let $x=(x_1, x_2, \dots x_n) \in \{0,1\}^n$ By $H(x)$ we mean the number of 1's in $(x_1, x_2, \dots x_n)$. Prove that $H(x) = \frac{1}{2} (n-\Sigma^n_{i=1} (-1)^{x_i})$....
go_editor
357
views
go_editor
asked
May 30, 2016
Quantitative Aptitude
descriptive
isi2014
quantitative-aptitude
proof
+
–
3
votes
1
answer
247
CMI2011-B-02a
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Show that for any subgraph $H$ of $G$, $H$ is good if and only if $G$ is good.
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good...
go_editor
577
views
go_editor
asked
May 19, 2016
Set Theory & Algebra
cmi2011
descriptive
graph-connectivity
proof
+
–
21
votes
5
answers
248
GATE CSE 1991 | Question: 17,a
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
Arjun
5.8k
views
Arjun
asked
Nov 15, 2015
Theory of Computation
gate1991
theory-of-computation
descriptive
identify-class-language
proof
+
–
48
votes
3
answers
249
GATE CSE 1991 | Question: 16-b
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
Arjun
4.4k
views
Arjun
asked
Nov 15, 2015
Graph Theory
gate1991
graph-theory
degree-of-graph
descriptive
proof
+
–
6
votes
1
answer
250
GATE CSE 1996 | Question: 9
The Fibonacci sequence $\{f_1, f_2, f_3 \ldots f_n\}$ is defined by the following recurrence:$f_{n+2} = f_{n+1} + f_n, n \geq 1; f_2 =1:f_1=1$Prove by induction that every third element of the sequence is even.
The Fibonacci sequence $\{f_1, f_2, f_3 \ldots f_n\}$ is defined by the following recurrence:$$f_{n+2} = f_{n+1} + f_n, n \geq 1; f_2 =1:f_1=1$$Prove by induction that ev...
Kathleen
1.3k
views
Kathleen
asked
Oct 9, 2014
Combinatory
gate1996
recurrence-relation
proof
descriptive
+
–
19
votes
3
answers
251
GATE CSE 1995 | Question: 24
Prove that in finite graph, the number of vertices of odd degree is always even.
Prove that in finite graph, the number of vertices of odd degree is always even.
Kathleen
5.8k
views
Kathleen
asked
Oct 8, 2014
Graph Theory
gate1995
graph-theory
degree-of-graph
proof
descriptive
+
–
11
votes
3
answers
252
GATE CSE 1995 | Question: 23
Prove using mathematical induction for $n \geq 5, 2^n > n^2$
Prove using mathematical induction for $n \geq 5, 2^n n^2$
Kathleen
1.6k
views
Kathleen
asked
Oct 8, 2014
Set Theory & Algebra
gate1995
set-theory&algebra
proof
mathematical-induction
descriptive
+
–
27
votes
5
answers
253
GATE CSE 1995 | Question: 21
Let $G_1$ and $G_2$ be subgroups of a group $G$. Show that $G_1 \cap G_2$ is also a subgroup of $G$. Is $G_1 \cup G_2$ always a subgroup of $G$?.
Let $G_1$ and $G_2$ be subgroups of a group $G$.Show that $G_1 \cap G_2$ is also a subgroup of $G$.Is $G_1 \cup G_2$ always a subgroup of $G$?.
Kathleen
6.6k
views
Kathleen
asked
Oct 8, 2014
Set Theory & Algebra
gate1995
set-theory&algebra
group-theory
normal
descriptive
proof
+
–
20
votes
2
answers
254
GATE CSE 1995 | Question: 11
Let $L$ be a language over $\Sigma$ i.e., $L\subseteq \Sigma^*$. Suppose $L$ satisfies the two conditions given below. $L$ is in NP and For every $n$, there is exactly one string of length $n$ that belongs to $L$. Let $L^c$ be the complement of $L$ over $\Sigma^*$. Show that $L^c$ is also in NP.
Let $L$ be a language over $\Sigma$ i.e., $L\subseteq \Sigma^*$. Suppose $L$ satisfies the two conditions given below.$L$ is in NP andFor every $n$, there is exactly one ...
Kathleen
3.7k
views
Kathleen
asked
Oct 8, 2014
Theory of Computation
gate1995
theory-of-computation
normal
decidability
proof
descriptive
+
–
18
votes
2
answers
255
GATE CSE 1994 | Question: 15
Use the patterns given to prove that $\sum\limits_{i=0}^{n-1} (2i+1) = n^2$ (You are not permitted to employ induction) Use the result obtained in (A) to prove that $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$
Use the patterns given to prove that$\sum\limits_{i=0}^{n-1} (2i+1) = n^2$(You are not permitted to employ induction)Use the result obtained in (A) to prove that $\sum\li...
Kathleen
2.0k
views
Kathleen
asked
Oct 5, 2014
Combinatory
gate1994
combinatory
proof
summation
descriptive
+
–
17
votes
3
answers
256
GATE CSE 1994 | Question: 5
A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n$ internal nodes is $2(n+1)$.
A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n...
Kathleen
12.9k
views
Kathleen
asked
Oct 5, 2014
DS
gate1994
data-structures
tree
proof
descriptive
+
–
4
votes
1
answer
257
Toc theorem proof
How $\phi^*=\epsilon$?
How $\phi^*=\epsilon$?
Bhagirathi
1.1k
views
Bhagirathi
asked
Oct 4, 2014
Theory of Computation
theory-of-computation
regular-expression
proof
+
–
18
votes
3
answers
258
GATE CSE 1993 | Question: 18
Show that proposition $C$ is a logical consequence of the formula$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$using truth tables.
Show that proposition $C$ is a logical consequence of the formula$$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$$using truth tables....
Kathleen
3.2k
views
Kathleen
asked
Sep 29, 2014
Mathematical Logic
gate1993
mathematical-logic
normal
propositional-logic
proof
descriptive
+
–
41
votes
3
answers
259
GATE CSE 1997 | Question: 21
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where $L^P = \left\{s \mid ss' \in L \text{ some string }s'\right\}$ $L^R = \left\{s \mid s \text{ obtained by reversing some string in }L\right\}$
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where$L^P = \left\{s \mid ss' ...
Kathleen
5.3k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
finite-automata
proof
+
–
22
votes
3
answers
260
GATE CSE 1997 | Question: 16
A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most $1$. The distance of a node from the root is the length of the path from the root to the ... height $h \geqslant 1$, how many nodes are at distance $h-1$ from the root? Write only the answer without any explanations.
A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most $1$. The distance...
Kathleen
5.0k
views
Kathleen
asked
Sep 29, 2014
DS
gate1997
data-structures
binary-tree
normal
descriptive
proof
+
–
19
votes
4
answers
261
GATE CSE 1997 | Question: 14
Let $R$ be a reflexive and transitive relation on a set $A$. Define a new relation $E$ on $A$ as $E=\{(a, b) \mid (a, b) \in R \text{ and } (b, a) \in R \}$ Prove that $E$ is an equivalence relation on $A$. Define a relation $\leq$ on the equivalence ... $\exists a, b$ such that $a \in E_1, b \in E_2 \text{ and } (a, b) \in R$. Prove that $\leq$ is a partial order.
Let $R$ be a reflexive and transitive relation on a set $A$. Define a new relation $E$ on $A$ as$E=\{(a, b) \mid (a, b) \in R \text{ and } (b, a) \in R \}$Prove that $E$ ...
Kathleen
3.9k
views
Kathleen
asked
Sep 29, 2014
Set Theory & Algebra
gate1997
set-theory&algebra
relations
normal
proof
descriptive
+
–
13
votes
3
answers
262
GATE CSE 1999 | Question: 14
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology. Let $A$ be a tautology and $B$ any other formula. Prove that $(A \vee B)$ is a tautology.
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.Let $A$ be a tautology and $B$ any other formula. Prove that $(A \ve...
Kathleen
2.4k
views
Kathleen
asked
Sep 23, 2014
Mathematical Logic
gate1999
mathematical-logic
normal
propositional-logic
proof
descriptive
+
–
34
votes
2
answers
263
GATE CSE 1999 | Question: 7
Show that the language $L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$ is not context free. $c$ is not $0$ or $1$.
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.
Kathleen
5.1k
views
Kathleen
asked
Sep 23, 2014
Theory of Computation
gate1999
theory-of-computation
context-free-language
normal
proof
+
–
33
votes
5
answers
264
GATE CSE 1999 | Question: 5
Let $G$ be a connected, undirected graph. A cut in $G$ is a set of edges whose removal results in $G$ being broken into two or more components, which are not connected with each other. The size of a cut is called its cardinality. A min-cut of $G$ is a cut ... $n$ vertices has a min-cut of cardinality $k$, then $G$ has at least $\left(\frac{n\times k}{2}\right)$ edges.
Let $G$ be a connected, undirected graph. A cut in $G$ is a set of edges whose removal results in $G$ being broken into two or more components, which are not connected wi...
Kathleen
6.4k
views
Kathleen
asked
Sep 23, 2014
Graph Theory
gate1999
graph-theory
graph-connectivity
normal
descriptive
proof
+
–
9
votes
1
answer
265
GATE CSE 1999 | Question: 4
Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$. Show that $|aH| = |bH|.$ Show that for every pair of elements $a, b \in G$, either $aH = bH$ or $aH$ and $bH$ are disjoint. Use the above to argue that the order of $H$ must divide the order of $G.$
Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$.Show that $|aH| = |bH|.$Show that for every pair of elem...
Kathleen
3.2k
views
Kathleen
asked
Sep 23, 2014
Set Theory & Algebra
gate1999
set-theory&algebra
group-theory
descriptive
proof
+
–
33
votes
1
answer
266
GATE CSE 1992 | Question: 16
Which of the following three statements are true? Prove your answer. The union of two recursive languages is recursive. The language $\{O^n \mid n\text{ is a prime} \}$ is not regular. Regular languages are closed under infinite union.
Which of the following three statements are true? Prove your answer.The union of two recursive languages is recursive.The language $\{O^n \mid n\text{ is a prime} \}$ is ...
Kathleen
8.6k
views
Kathleen
asked
Sep 13, 2014
Theory of Computation
gate1992
theory-of-computation
normal
closure-property
proof
descriptive
+
–
40
votes
4
answers
267
GATE CSE 1992 | Question: 14a
If $G$ is a group of even order, then show that there exists an element $a≠e$, the identity in $G$, such that $a^2 = e$.
If $G$ is a group of even order, then show that there exists an element $a≠e$, the identity in $G$, such that $a^2 = e$.
Kathleen
7.2k
views
Kathleen
asked
Sep 13, 2014
Set Theory & Algebra
gate1992
set-theory&algebra
group-theory
normal
descriptive
proof
+
–
15
votes
5
answers
268
GATE1991-15,a
Show that the product of the least common multiple and the greatest common divisor of two positive integers $a$ and $b$ is $a\times b$.
Show that the product of the least common multiple and the greatest common divisor of two positive integers $a$ and $b$ is $a\times b$.
Kathleen
2.0k
views
Kathleen
asked
Sep 12, 2014
Set Theory & Algebra
gate1991
set-theory&algebra
normal
number-theory
proof
descriptive
+
–
Page:
« prev
1
...
4
5
6
7
8
9
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register