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.

Filter by
Sorted by
Tagged with
0
votes
0answers
22 views

Double induction and generalizations

Let $p = p(n,m)$ be a property that depends on $n,m \in \mathbb{N}$. If we want to show that it is true using ordinary induction, we see that $p$ holds for all $n,m \geq 1$ iff the property $$Q(n) := \...
0
votes
0answers
28 views

Combinatorial number system alternate proof

The Combinatorial number system is the theorem that every positive integers can be expressed as the combination of a using a unique sequence of of a strictly decreasing sequence $c_k > ... c_2 > ...
0
votes
0answers
11 views

well founded induction / difference to strong induction

We are given a chocolate bar with $n$ pieces (squares) and we already know by strong induction that $n-1$ are needed to break it in individual parts. https://web.stanford.edu/class/archive/cs/cs103/...
0
votes
0answers
23 views

show by induction that $ \cap_{p}{\text{clco}}\cup_{m\geq p}\frac{1}{m}\sum_{n=1}^{m}{C_n}\subset \cap_{p}\text{clco}\cup_{n\geq p}{C_n}. $

Let $X$ be a separable Banach space, and we consider the collection: $$ \mathcal{P}_{wkc}(X)=\{C\in 2^X: C \text{ is nonempty convex weakly compact subset of }X\} $$ By $w$ we shall indicate the weak ...
2
votes
0answers
68 views

we want to prove that $(n,n+1) \cap \mathbb{N}$ is empty [duplicate]

Problem: prove that for each $n \in \mathbb{N}$ : $(n,n+1) \cap \mathbb{N} = \varnothing $ attempt: Indeed, let $S(n)$ be the statement $\{ n : (n,n+1) \cap \mathbb{N} = \varnothing \}$. Clearly, $(...
0
votes
0answers
11 views

Inductive proof on increasing coefficients

If I have two polynomials, $$a_nx^n+....+a_1x+a_0$$ and $$ b_nx^n+....+b_1x+b_0$$ and I want to show that the rate of which the coefficients are increasing, start from the $x^n$ term in the first ...
0
votes
1answer
31 views

Statement true for all prime numbers — can this be done by Math Induction?

Let's say that you want to prove a statement is true for all prime numbers. Can this be done by Math Induction?
2
votes
0answers
37 views

Proof by induction check

The question I am attempting is broken up into 2 parts: a) Prove that $(1+2+...+n)^2 = 1^3 + 2^3 +...+n^3$ b)Find a proof for the Bernoulli inequality: $$(1+x)^n \geq1+nx \space \text{for all}\...
0
votes
2answers
32 views

Simple proof by induction problems

I just started learning proof by induction and I have come across 2 problems that I am not sure if am doing right. The first one is Prove that $11^n - 1$ is dividable by $10$. I started with ...
0
votes
0answers
16 views

arranging binary words in circle - induction

i need to prove that for set A which contains all of the binary words of length n can be arranged in a circle so each two adjacent words will be different only by one char. I tried solving it by ...
1
vote
3answers
48 views

Why are there multiple base cases in this strong induction? [duplicate]

My understanding of needing a base case, in general, is that after proving the induction step, we can assert that the proposition is true for all values from the base case. This question ($∀n ∈ Z, n≥...
0
votes
1answer
22 views

Divisibility proof by induction using modular arithmetics

I need to prove that $ 7 \mid 3^{2n} - 2^n $ for every natural $n$. I have used induction on the modular expression $ 3^{2n} - 2^n \equiv 0 \bmod (7) $; the base case is trivial, and the thesis is $$...
0
votes
2answers
44 views

If even function then … [duplicate]

We let {$a_n$}$_{n\in N}$ be $a_n$=$\frac{f^{n}(0)}{n!}$. I have to show that if $f$ is an even function so is $a_{2n-1}$$=0$ for all n$\in$N. How can I show it? By induction maybe? Can anyone give a ...
0
votes
2answers
35 views

Verifying a Topological Property

Let (X,T) be any Topological Space. Verify that Intersection of any finite number of members of T is a member of T. I tried to prove using that intersection of any two sets of T belongs to T. So the ...
2
votes
1answer
73 views

Prove that for $n \geq 5, f_{n}+f_{n-1}-1$ has at least $n+1$ prime factors

Question - Prove that for $n \geq 5, f_{n}+f_{n-1}-1$ has at least $n+1$ prime factors, where $f_{n}=2^{2^{n}}+1$ My proof - I proved it using induction,but i got stucked in base case step, for $n=...
1
vote
0answers
37 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 ...
0
votes
0answers
18 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 ...
0
votes
2answers
35 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 ...
0
votes
4answers
58 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}$
1
vote
1answer
46 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 ...
1
vote
1answer
36 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 difficulty ...
0
votes
0answers
22 views

Find the formula of a succession [closed]

$$S_n = \sum_{k=1}^n \frac{1}{(k+0.1)^k}\,.$$ Is there an explicit analytic formula for $S_n$ for any value of $n$?
0
votes
1answer
28 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 ...
0
votes
1answer
32 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) $
2
votes
1answer
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 ...
0
votes
0answers
43 views

Proof for any positive integers n>7 can be written as the sum of three or fewer squares of positive integers. [closed]

Prove that for any positive integer n>7 can be written as the sum of three or fewer squares of positive integers. How will I go about this. I'm lost.
0
votes
1answer
184 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?
0
votes
1answer
124 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....
1
vote
0answers
31 views

Inductive proof on sign of coefficients involving series and product

I'm interested in showing by induction that if I have a product of geometric series and a product of binomials that if for some $x^i$ which has coefficient $a_i$ and I know $a_i$ is positive then $a_{...
0
votes
1answer
52 views

induction for the collatz conjecture for $n=2^k$

Prove / disprove the following statements regarding the Collatz conjecture T $(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \rightarrow T(n)=1)$ $(1) \forall n \in \...
1
vote
3answers
51 views

Proof verification: Showing, through Induction, that a set $S=\mathbb{N}$

Let $S\subseteq \mathbb{N}$ where: (i) $2^k\in S$ for all $k\in \mathbb{N}$; and (ii) for all $k\ge 2$, if $k\in S$, then $k-1\in S$. Prove using induction that $S=\mathbb{N}$. So the base case: If $...
-1
votes
1answer
33 views

Math Induction proof union and intersections

I'm totally new to Math Induction. I have a question on using Math Induction proof with union and intersections. Here's the initial problem: Prove that, for if C, D1, D2, …, Dn are n + 1 sets, that $...
-3
votes
1answer
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 ...
0
votes
1answer
24 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-...
2
votes
3answers
92 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 ...
-2
votes
0answers
19 views

Use mathematical induction to prove $\sum_{k=0}^n 2^k = 2^{n+1} − 1$ that for all integer $n \geq 0$. [duplicate]

Have to do mathematical induction this, but not certain how to? Anyone could help? $$ \sum_{k=0}^n 2^k = 2^{n+1} − 1, n\geq 0$$
5
votes
3answers
91 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 ...
1
vote
2answers
21 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 ...
0
votes
3answers
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.
1
vote
1answer
49 views

Show if $x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$, then $1\le x_n \le 2$ for all $n\in\mathbb{N}$ using Strong Induction

Let $x_1=1$, $x_2=2$, and $x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$. Show using strong induction that $x_n\in [1,2]$ for all natural $n$. So I know just from inequalities that if $a<b$ then $a<\frac{...
-2
votes
1answer
37 views

Proving by induction that $(5^{2n})-1$ is divisible by $8$ and $3$ [duplicate]

Prove by induction that for all integers n that $5^{2n}-1$ is divisible by $8$ and $3$. Explain
1
vote
1answer
49 views

Proving finite amount of 'non-cool' numbers

We will call a natural number $n \in \mathbb{N}$ 'cool' if two natural numbers $t,k \in \mathbb{N}$ exist such that $n = 4t + 7k$ For example: 8 and 26 are cool because: $ 4 \cdot 2 + 7 \cdot 0 = 8$ ...
2
votes
3answers
44 views

In one-step induction, why sometimes there are 2 base cases?

I noticed in various induction proofs, that it uses 2 base cases (e. g: for $n = 1$ and $2$ the problem trivially holds...) Why is that? Isn't one base case enough for one-step induction?
0
votes
1answer
35 views

Prove an algorithm on the Thue-Morse sequence by induction

For the purposes of this question, I'm subscribing to the following definition of the Thue-Morse sequence: Let $T_0 = 0$, and $C$ be the bitwise complement function. $T_n = T_{n - 1} + C(T_{n - 1})$. ...
0
votes
2answers
30 views

Proof of divisibility by induction [duplicate]

I've recently come across a divisibility problem that I am unable to solve. I know that most of these types of problems have fairly straightforward proof-by-induction solutions -- but for this ...
0
votes
5answers
63 views

Proving the series $s_n=1+\frac{1}{\sqrt2}+\cdots +\frac{1}{\sqrt n}$ is not bounded [duplicate]

Let $s_n=1+\frac{1}{\sqrt2}+\cdots +\frac{1}{\sqrt n}$. This sequence is definitely increasing, and I tried to show that it is not bounded above, by induction. However if $s_n\leq2$, then $s_{n+1}\...
2
votes
0answers
29 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 ...
0
votes
3answers
33 views

Prove by mathematical induction that $\vert z_1 \cdot z_2 \cdots z_n \vert = \vert z_1 \vert \vert z_2 \vert \cdots \vert z_n \vert$

I am having some trouble with a mathematical induction proof. The question is the following: Prove by mathematical induction that $\vert z_1 \cdot z_2 \cdot z_3 \cdots z_n \vert = \vert z_1 \vert \...
0
votes
1answer
41 views

Disparity between Induction and Well-ordering Principles

Over classical logic, the induction and well-ordering schemas are equivalent. These schemas state the following, given any linear ordering $(W,<)$ and property $Q$ on $W$: Induction: $∀k{∈}W\ ( \...
-2
votes
1answer
21 views

I need help with this “hard” induction proof problem [duplicate]

"Use mathematical induction to prove this binomial formula where z1 and z2 are two complex numbers and n is a positive integer (n= 1,2,...)" this is my translation of the problem

1
2 3 4 5
159