# Questions tagged [induction]

For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the base case, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant for questions about induction over natural numbers but is also appropriate for other kinds of induction such as transfinite, structural, double, backwards, etc.

8,002 questions
Filter by
Sorted by
Tagged with
22 views

40 views

### proof by induction : graph does not contain Kr+1 as a subgraph, has no more than ? edges

So I have to prove by induction in the number of the vertices of the graph this sentence: Let r$\ge$ 2. i)Use (strong) induction in the number of vertices to prove that, for n$\ge1$ every ( simple ...
22 views

### Proof for Gossip problem

Suppose there are n people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information ...
36 views

### For an induction proof involving sigma starting at 0 can our base case be non-zero?

I am trying to prove the claim to be true for any number n, but I am having a little bit of a problem. If the summation starts from i = 0 can we use 1 for our base case? Because I can see how I can ...
65 views

### Show that for all $n ≥ 2$ it is true: $1^3+2^3+\cdots+(n-1)^3<\dfrac{n^4}{4}$ [closed]

How can I prove that? $1^3+2^3+\cdots+(n-1)^3<\frac{n^4}{4}$
53 views

### General method to solve the given question.

A question came in my test and I was not able to solve it. An aeroplane has $100$ seats (numbered $1$ to $100$) and $100$ passengers waiting to board each having a ticket with a number from $1$ to ...
38 views

### Is it “propositional function” or simply “proposition”

I was going through the text "Discrete Mathematics and Its Application" by Kenneth H Rosen (5th Edition) where I came across the use of $P(n)$ in the mathematical induction chapter and felt ...
29 views

### Use structural induction to prove that $v(G) = e(G) + 1$

$G$ is an element of FBRT (full binary rooted trees), $v(G)$ = total vertices in $G$, and $e(G)$ = total edges in $G$. I know logically that this is true, but I'm not sure how to prove it using ...
35 views

### Prove using mathematical induction that for all $n! \ge 2^{n-1}$ [duplicate]

Prove using mathematical induction that for all $n! \ge 2^{n-1}$ Base case, p(1), 1! >= 1 $p(n+1), n!(n+1) \ge 2^{n-1}(n+1)$
117 views

### Help to inductively define finite trees

In my assignment, I have an in-depth question regarding finite trees. We are presented with the trees in list form, and an empty list is symbolized as $\emptyset$. Example: A symmetrical tree with ...
220 views

### Express $\sum_{i=0}^n (3𝑖^3 − 6𝑖 + 2)$ as a polynomial $p(n)$

How would I express $\sum_{i=0}^n (3𝑖^3 − 6𝑖 + 2)$ as a polynomial $p(n)$ and also prove that the sum equals $p(n)$ using induction?
129 views

### Herbrand Logic exercise on multidimensional induction

I am completing a self study guide from Stanfords "Teach yourself Logic" course, and I am stuck on a problem regarding multidimensional induction. "Starting with the axioms for e given in Section 12....
31 views

53 views

37 views

### Mathematical induction method for a problem [closed]

Well, I've got a math problem and for me it's so difficult, so if u don't mind to help it would be amazing <3, its about the mathematical induction method and the ecuation is this: Use the ...
27 views

### Floyd Invariant Principle on a deck of cards [closed]

The below problem has been taken from Mathematics for Computer Science (MIT Opencourseware https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-...
97 views

### Prove by induction that for all $n\in\mathbb N, (\sqrt3+i)^n+(\sqrt3-i)^n=2^{n+1}\cos(\frac{n\pi}6)$

I want to prove by induction that for all $n \in \mathbb{N}$, $$(\sqrt{3} + i)^n + (\sqrt{3} - i)^n = 2^{n+1} \cos\left(\frac{n\pi}{6} \right)$$ I can prove the identity using direct complex number ...
93 views

### Recursive sequence, $x_{1} \geq 0, x_{n+1}=\sqrt{x_{n}+2}$

Recursive sequence, $x_{1} \geq 0, x_{n+1}=\sqrt{x_{n}+2}$ and it is requested to prove that $\lim_{n \to \infty} x_n=2$. This is a common problem, but I found it quite more difficult when the value ...
22 views

### Convergence of two nested geometric sequences

Let $\nu_t = b^t \nu_0$ be a geometric sequence where $\nu_0>0$, $0<b<1$, $t = 0,1,2,\dots$. Let $h_0>0$ and $0<a<1$. Define the sequence $h_{t+1} = a h_t+\nu_t$. Show that $h_n$ is ...
53 views

### Prove that $\sum_{i=0}^{n-1} {2^i} = 2^n -1$ [duplicate]

I need to prove that $$\sum_{i=0}^{n-1} {2^i} = 2^n -1.$$ I tried induction but something didn't work.
50 views

31 views

### Inductive closure of a relation?

I did not really know whether to ask this here or in MathOverflow. On the one hand, I have a maths degree and this is part of my PhD research on computer science, and I am pretty sure this is not a ...
34 views

37 views

### Is this the correct inductive step to prove that the n-th derivative of ln(2x+1) is equal to my formula?

I deduced that the n-th derivative is given through $f(x)^n=(-1)^{n+1}*\frac{2*2^{n-1}}{(2*x+1)^n}$. Is the correct inductive step $f(x)^{n+1}=(-1)^{n+2}*\frac{2*2^{n}}{(2*x+1)^{n+1}}$?
38 views

### Prove $3^{n}> n^{2}$ for $n=2$ by induction

I understand base case at $n=1$, and $n=2$. Then I do understand the inductive hypothesis of assuming $n=k$. The part that confuses me is when showing $n=k+1$. On other tutorials that are online, they ...
40 views

### $a_1, a_2, a_3 \dots$ is defined by $a_1 = 1$, $a_2 = 1$, $a_3 = 1$, $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for $n ⩾ 4$. Prove that $a_n < 2^n$.
The sequence $a_1, a_2, a_3, \ldots$ is defined by $a_1 = 1, a_2 = 1, a_3 = 1, a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for $n\geq 4$. Using mathematical induction correctly, prove that $a_n < 2^n$ for ...