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.
10,347 questions
3
votes
1
answer
145
views
Number of real roots of the n-th iteration of $f(x) = x^3 - 3x + 1$
Given, $$f(x) = x^3 - 3x + 1$$
I was solving a problem to find the number of distinct real roots of the composite function $f(f(x)) = 0$.
By analyzing the graph of $f(x)$, we can observe the local ...
- 964
10
votes
5
answers
1k
views
Why Does Tao Use Inductive Language When Giving Recursive Definitions?
I’ve read similar questions, but the answers I found were either contradictory or too advanced for my current level. I’m a computer engineering student, and I’m trying to understand a point in Terence ...
- 111
-1
votes
1
answer
60
views
A conceptual question about induction
I was doing a problem. It asks for showing the determinant of a matrix defined by $(a_{ij})$ and prove that the relation $$\text{det}(A_{n+2})-2\cos(\theta)\text{det}(A_{n+1})+\text{det}(A_n)=0 \tag{1}...
- 424
4
votes
0
answers
93
views
Can probability theory be made fully computable?
I’ve been reading about objective Bayesian theories lately and came upon the concept of universal priors and specifically, the Solomonoff prior. This seemed to answer my initial query about whether a ...
3
votes
1
answer
238
views
Inductive proof of necessary and sufficient conditions for diagonalisability
I am very confused by the following highlighted lines in a proof of necessary and sufficient conditions for diagonalisability in Linear Algebra Done Right (4th ed.), Axler S. (2024).
Questions.
How ...
- 1,106
0
votes
0
answers
108
views
Demonstration of $ \left( 1+\varepsilon \right)^{x}\ge1+x\varepsilon $
consulting:
Proof by induction of Bernoulli's inequality $ (1+x)^n \ge 1+nx$
Simil Bernoulli inequality for induction
I follow a proccedure on we Let $ \varepsilon\gt-1 $ and $ x $ a positive ...
0
votes
1
answer
67
views
How can I define an infinite sequence by induction and prove its existence? [closed]
To prove by induction that there exists a sequence $(a_n)_{n\in\mathbb{N}}$ verifying a specific condition I can think of two possible statements;
$P_n$ : $(a_i)_{i \in \mathbb{N}, i \le n}$ is ...
- 11
0
votes
1
answer
200
views
Is there induction in (the internal logic of) an arbitrary elementary topos $\mathcal{E}$?
The Question:
Is there induction${}^\dagger$ in (the internal logic of) an arbitrary elementary topos $\mathcal{E}$?
$\dagger$: By which I mean: "Is there an induction principle . . .". ...
- 48.5k
-2
votes
2
answers
430
views
Can it be proved that $\mathbb{N}\subseteq e$ if we can prove $0\in e$, $1\in e$, etc. separately?
Suppose for every natural number $n$, $Z_n(x)$ is a first order predicate with a single free variable $x$ that states, informally, that $x = n$. For instance $Z_0(x)$, stating that $x = 0$, i.e. that $...
- 12k
-2
votes
2
answers
115
views
Prove: $7 \mid 5^{2n} + 3 \cdot 2^{5n - 2}, \quad \text{for } n \ge 1 $ [duplicate]
Prove: $ 7 \mid 5^{2n} + 3 \cdot 2^{5n - 2}, \quad \text{for } n \ge 1 $
I saw this problem on David Burton Elementary Number Theory book. This exact question has been asked before on this website ...
- 29
0
votes
1
answer
46
views
Prove the Commutative Property of Addition for Finite Sums
I am trying to solve the problem $2.2.11$ in the book A Course in Mathematical Analysis by D. J. H. Garling. I will restate the problem as follow:
"Suppose that $\left(a_1, a_2, \cdots, a_n\right)...
1
vote
0
answers
80
views
Sequence of polynomials defined by recursion
Consider the following sequence of even polynomials $f_k:[0,1]\to\mathbb R$ ,
$$ \begin{cases} \,f_k(x)\,= \frac{(1-x^2)^2}{2}\,f_{k-1}''(x) \quad \textrm{for } k\geq 2\\ f_1(x)=x^2
\end{cases}$$
I ...
- 951
2
votes
1
answer
79
views
Can induction and coinduction be generalized into a single principle?
Let $s$ and $t$ be monotonic operators on sets of $D$. Let $A$ (and $B$) be the least (and greatest) fixed point of $s$ (and $t$).
Finally let $P \subseteq D$.
All of these imply $A \subseteq P$:
\...
- 299
-1
votes
1
answer
86
views
Bypassing binomial theorem to proving inequality
I wanted to prove the following inequality by induction that for all integers $n\ge 2$ ,
$$\left(\dfrac{n+1}{2} \right)^n \ge n!$$
In finalizing the inductive step, we need to prove this
$$\left(1+\...
- 87
3
votes
1
answer
95
views
Show that $|a_n(x)/a_n(1/x)| = 1$
Assume that $a_0(x)$ is a rational function such that $|a_0(x)/a_0(1/x)| = 1$ and define the sequence $a_n(x)$ such that $a_n(x) = x(a_{n-1}(x))'$ if $n \in \mathbb{N}$. It follows that $|a_n(x)/a_n(1/...
- 911