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
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
48 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
38 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
78 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
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
4answers
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}$
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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) $
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
1answer
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?
0
votes
1answer
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....
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
54 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
53 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
36 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
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-...
2
votes
3answers
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 ...
5
votes
3answers
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 ...
1
vote
2answers
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 ...
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
50 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
39 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
50 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
47 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
37 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
34 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
76 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
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 ...
0
votes
3answers
34 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
42 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\ ( \ βˆ€...
0
votes
1answer
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}}$?
-1
votes
2answers
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 ...
-1
votes
1answer
40 views

Double Induction Example

I've been looking at examples of problems using double induction and have found one that has stumped me. Here is the problem: Let $n,m\in \mathbb{N}$. Let $P(n,m)$ denote the statement $n>m \...
-1
votes
1answer
48 views

Induction Proof Clarification

$T= \{3^0, \ldots, 3^{k-1}\}, t>0$. We know that $T \in P(T)$ and for any $A \in P(T), A \subseteq T$ and further for any $B \in P(A) \subset P(T)$ which implies $B \subset T$. So if we consider $...
-1
votes
1answer
46 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 ...
0
votes
2answers
71 views

Induction problem clarification

here's the problem I'm doing: Prove that for all integers $n$ with $n \geq 1$, we have $n \cdot 6^n \leq (n+10)!$ I don't understand how to get from [$6 \cdot (k + 10)! + 6^{k+1}$] to $k \cdot (k + ...
1
vote
2answers
39 views

Use mathematical induction to prove n β‰₯ 3

I have proved for n =3, and assumed S(k) is true already. I have gotten all the way to the induction step of S(k+1) = 3+4+5+...+(k+1) = ((k+1-2)(k+1+3))/2 I am having trouble proving it past this ...
0
votes
1answer
32 views

Proof by Induction: Bicolor Little Squares Arrangements

I would like to prove by induction that the number of arrangements that one can create with A little squares with either two colors (Black or White): is given by this formula: $$ a = \sum_{n=0}^A ...
3
votes
2answers
55 views

If $\alpha, \beta$ are the roots of the equation $x^2-(p+1)x+1=0.$ show that $\alpha^n + \beta^n$ is not divisible by $p$ $(p \ge3)$

Let $p \ge 3$ be an integer and $\alpha, \beta$ are the roots of the equation $x^2-(p+1)x+1=0.$ Using mathematical induction show that $\alpha^n + \beta^n$ (i) is an integer (ii) is not divisible by ...
0
votes
1answer
48 views

How do I prove this property for ratio?

If $\frac{a_1}{b_1}$, $\frac{a_2}{b_2}$, $\frac{a_3}{b_3}$, $\dots, \frac{a_n}{b_n}$ are unequal fractions. All numbers are positive. Then the ratio: $$\frac{(a_1+a_2+\dots+a_n)}{(b_1+b_2+\dots+b_n)...
0
votes
1answer
38 views

Proving Fibonacci sequence by induction method

I am trying to make a conjecture as to Fibonacci numbers which are divisible by 3 and trying to prove it by mathematical induction where the initial conditons are 0 and 1. My problem is that I ...
1
vote
3answers
26 views

Induction step: $5 + 5n \leq {n}^2$ for $n \geq 6$

Prove by mathematical induction that $5 + 5n \leq {n}^2 $ for all integers $n\geq 6$. Step 1: Base case Suppose $n = 6$, hence $5 + 5(6) \leq {6}^2 = 35 \leq 36$ We proved that base case is true as ...
-1
votes
3answers
131 views

Prove $\frac{11n^3 + 25n}{6}$ is an integer [duplicate]

Prove by induction that for every integer n, $\frac{11n^3 + 25n}{6}$ is an integer (i cant post the actual given expression since it might cause academic offence). I have only worked with proofs with ...
0
votes
1answer
25 views

Prove by Induction - Modular arithmetic with Logarithms

\begin{align} X_1 &= 3 \\ X_2 &= 3^3 \\ X_3 &= 3^{3^3} \end{align} Prove by induction that $X_n \equiv 3 \mod{4}$, for all $n \geq 1$. My attempt at the induction step: We ...
1
vote
1answer
26 views

Proving for any nonnegative integer $k$, $[T^k]_\beta=([T]_\beta)^k.$

My path for this problem is completely wrong as operators in general are non-diagonizable. Thus, I was wondering if someone can please help me prove it? Thank you! Let $\beta$ be an ordered basis for ...

1 2
3
4 5
…
161