Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
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.
makhdoom ghaya
asked
in
Combinatory
Nov 29, 2016
by
makhdoom ghaya
6.9k
views
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))$
makhdoom ghaya
asked
in
Mathematical Logic
Nov 14, 2016
by
makhdoom ghaya
5.1k
views
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.
makhdoom ghaya
asked
in
Graph Theory
Nov 14, 2016
by
makhdoom ghaya
1.8k
views
gate1987
graph-theory
degree-of-graph
descriptive
proof
1
vote
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}$
go_editor
asked
in
Combinatory
Jun 3, 2016
by
go_editor
537
views
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}$
go_editor
asked
in
Geometry
Jun 3, 2016
by
go_editor
302
views
isi2011
descriptive
proof
trigonometry
non-gate
1
vote
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})$.
go_editor
asked
in
Quantitative Aptitude
May 30, 2016
by
go_editor
347
views
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.
go_editor
asked
in
Set Theory & Algebra
May 19, 2016
by
go_editor
552
views
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.
Arjun
asked
in
Theory of Computation
Nov 15, 2015
by
Arjun
5.8k
views
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.
Arjun
asked
in
Graph Theory
Nov 15, 2015
by
Arjun
4.3k
views
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.
Kathleen
asked
in
Combinatory
Oct 9, 2014
by
Kathleen
1.3k
views
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.
Kathleen
asked
in
Graph Theory
Oct 8, 2014
by
Kathleen
5.7k
views
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$
Kathleen
asked
in
Set Theory & Algebra
Oct 8, 2014
by
Kathleen
1.5k
views
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$?.
Kathleen
asked
in
Set Theory & Algebra
Oct 8, 2014
by
Kathleen
6.5k
views
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.
Kathleen
asked
in
Theory of Computation
Oct 8, 2014
by
Kathleen
3.7k
views
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}$
Kathleen
asked
in
Combinatory
Oct 5, 2014
by
Kathleen
2.0k
views
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)$.
Kathleen
asked
in
DS
Oct 5, 2014
by
Kathleen
12.9k
views
gate1994
data-structures
tree
proof
descriptive
4
votes
1
answer
257
Toc theorem proof
How $\phi^*=\epsilon$?
Bhagirathi
asked
in
Theory of Computation
Oct 4, 2014
by
Bhagirathi
1.1k
views
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.
Kathleen
asked
in
Mathematical Logic
Sep 29, 2014
by
Kathleen
3.1k
views
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\}$
Kathleen
asked
in
Theory of Computation
Sep 29, 2014
by
Kathleen
5.3k
views
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.
Kathleen
asked
in
DS
Sep 29, 2014
by
Kathleen
5.0k
views
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.
Kathleen
asked
in
Set Theory & Algebra
Sep 29, 2014
by
Kathleen
3.9k
views
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.
Kathleen
asked
in
Mathematical Logic
Sep 23, 2014
by
Kathleen
2.4k
views
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$.
Kathleen
asked
in
Theory of Computation
Sep 23, 2014
by
Kathleen
5.1k
views
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.
Kathleen
asked
in
Graph Theory
Sep 23, 2014
by
Kathleen
6.4k
views
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.$
Kathleen
asked
in
Set Theory & Algebra
Sep 23, 2014
by
Kathleen
3.1k
views
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.
Kathleen
asked
in
Theory of Computation
Sep 13, 2014
by
Kathleen
8.6k
views
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$.
Kathleen
asked
in
Set Theory & Algebra
Sep 13, 2014
by
Kathleen
7.2k
views
gate1992
set-theory&algebra
group-theory
normal
descriptive
proof
Page:
« prev
1
...
4
5
6
7
8
9
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged proof
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...