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 ...

learn more… | top users | synonyms

14
votes
0answers
353 views

Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
8
votes
0answers
355 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
5
votes
0answers
127 views

Sum of like powers equal to a power

It's not hard to prove that $$(1+2+3+\ldots+n)^2=1^3+2^3+\ldots+n^3$$ ( for example using induction ) A generalization of this is also known : $$(\sum_{d \mid n} \tau(d))^2=\sum_{d \mid n} ...
4
votes
0answers
54 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also ...
4
votes
0answers
122 views

Using induction to prove a congruence?

Let $a = 2+\sqrt{3}.$ By analogy to complex numbers let R$(a)$ be $r,$ the non-surd part of $r + s\sqrt{3}.$ I would like to show that a necessary but by no means sufficient condition that ...
4
votes
0answers
80 views

Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

And we choose the positive and negative signs in a way that the equation becomes true. I think it can be proved with mathematical induction. So here's how I begin: For $n=1$, $1=+1^2$ which is true. ...
4
votes
0answers
101 views

Is this a valid statement that would imply the Collatz Conjecture?

Let $f$ denote the Collatz transformation: $f(x) = \left\{ \begin{array}{ll} {x\over 2} & \quad x\equiv 0 \mod 2 \\ 3x+1 & \quad x \equiv 1\mod 2 ...
4
votes
0answers
112 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) ...
4
votes
0answers
102 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
4
votes
0answers
196 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
4
votes
0answers
122 views

Transfinite induction and valuation rank

In Engler's valued fields, exercise 3.5.2 goes as follows Construct valuations on $\Bbb{C}$ of rank $\kappa$ for every cardinal $\kappa \leq 2^{\aleph_0}$. The idea behind this (for any ...
3
votes
0answers
45 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
3
votes
0answers
51 views

Prove $\binom{n}{k} = 0$ for $n = 0, 1, … , k-1$

It's a homework problem. Prove $\binom{n}{k} = 0$ for $n = 0, 1, ... , k-1$ I think induction needs to be used, I can do $n = 0$ (and $n = 1$ since our teacher likes us to do the first two), but $n ...
3
votes
0answers
50 views

Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
3
votes
0answers
49 views

Proof of Leibniz formula from Laplace expansion

I'm trying to prove Leibniz formula for the determinant using Laplace expansion. Here's my attempt: For a $1 \times 1$ matrix $A = \begin{pmatrix}a_{11}\end{pmatrix}$, define $\det A = a_{11}$. For ...
3
votes
0answers
43 views

Induction proof - not sure how to proceed with next step

Define two sequences $A_n, B_n$ as follows: \begin{align*} A_1 &= 1\\ A_2 &= 3\\ A_3 &= 2 \cdot 3+1=7 \\ A_4 &= 2 \cdot 7 + 3 = 17\\ A_5 &= 2 \cdot 17 + 7 = 41\\ A_n &= ...
3
votes
0answers
53 views

Verify my induction proof for Balanced Ternary expressions

In first place I apologize if you find a grammatical error, my English is not too good for now, but I'm work on it. That also goes for errors in my question (this is my first post). I encounter the ...
3
votes
0answers
69 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
3
votes
0answers
112 views

Cauchy-Euler Equation of order $n$

What I wish to prove is that for a Cauchy-Euler equation of order $n$, the substitution $x=e^{t}$ transforms it into a linear differential equation with constant coefficients. To put it as a theorem: ...
3
votes
0answers
622 views

Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
3
votes
0answers
236 views

Group-theoretic proof that an increasing multiplicative function is exponential

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that ...
2
votes
0answers
46 views

Knuth algorithm on constructing a proof

I'm going through mathematical induction section of Knuth's book "The Art of Computer Programming" (pg. 11). I'm having a hard time understanding Algorithm I on constructing a proof. Here is the ...
2
votes
0answers
44 views

Proof by Induction that relates to the Jacobian Determinant

Define $f_2$ : $ℝ$ $\to$ $ℝ^2$ by putting $$f_2 (\theta)=(\cos(\theta),\sin(\theta)),$$ and for n $\ge3$ define $f_n: ℝ^{n-1}\toℝ^n$ inductively by setting $$f_n=(\theta_1, ...
2
votes
0answers
22 views

How to find variance of k+1 elements if variance of k elements is known?

I need to find the variance of k+1 elements given the variance of k elements. I can also store other features for k elements like mean ($\mu_n$) etc. So, given the below function's value, $$ ...
2
votes
0answers
88 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
2
votes
0answers
70 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
27 views

Confusion on particular step in this weak induction proof

I am studying for a midterm, and I came across this proof. Use mathematical induction(weak) to show that for all integers n $\geq$ 2 , if x$_{1}$, x$_{2}$, ... x$_{n}$ are strictly between 0 and 1 ...
2
votes
0answers
84 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: $$\sum_{v ∈ V} deg(v) = ...
2
votes
0answers
109 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: Show with induction, that the $i^{\rm th}$ Fibonacci number satisfies the equality: $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
2
votes
0answers
211 views

Simple knapsack with arbitrary weights: Algorithm won't work, but my proof by induction doesn't agree.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of ...
2
votes
0answers
52 views

Proving the base case for a problem in elementary number theory

I have a question about how to prove statements such as the following, using induction: If $p \mid a_1a_2 \cdots a_k$, then $p \mid a_i$ for some $i$, $i = 1, 2, \ldots, k$, where $p$ is prime. ...
2
votes
0answers
92 views

Inequality sine power series

How can we show, for $k\geq 1$ and $x \geq 0$, the inequality below by induction? $\displaystyle \sin x \geq \sum_{n=1}^{2k} (-1)^{n+1} \frac 1{ (2n - 1)! }x^{2n-1} $ The base case $k = 1$ gives ...
2
votes
0answers
105 views

Rearranging numbered cards to reverse their order

I have been thinking about this question for a long time, but I can't solve it. Here is the question: We have $9$ cards, with numbers one to nine written on them (in the order $1, 2, \ldots , 9$). ...
2
votes
0answers
51 views

How to proceed to show this hold by induction?

Show that $$\frac3{1\cdot2\cdot4}+\frac4{2\cdot3\cdot5}+\dots+\frac{n+2}{n(n+1)(n+3)}=\frac16\left[\frac{29}6-\frac4{n+1}-\frac1{n+2}-\frac1{n+3}\right],\text{ for $n\in\mathbb N$}.$$ I try ...
2
votes
0answers
144 views

geomtry and induction Discrete Math

Claim: Suppose that we draw any number of straight lines in the plane, with the restriction that no two are parallel and no intersection point belongs to more than two lines. The lines divide up the ...
2
votes
0answers
62 views

Writing down the induction principle formally

Can one write principle of mathematical induction formally in the following way ($ P $ and $ S $ are a predicate and the successor function, respectively)? $$(\exists x\in\mathbb {N}(P (x))\wedge ...
2
votes
0answers
112 views

Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $$ {\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$} $$ It has been my ...
2
votes
0answers
76 views

Proof for a finite number of elements

if I want to proof something for a restricted finite number of elements, meaning the following: Imagine that I have a theorem that is somehow similar to the following: For each element in ...
2
votes
0answers
72 views

monotonicity proof - double induction

Suppose we have 4 functions depending on a variable $x$ : $a(x), b(x), c(x)$ and $d(x)$. I want to prove that $a(x) - c(x)$ is monotonically increasing in $x$, by an induction argument. Also I want ...
2
votes
0answers
218 views

Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom: $$\forall x \forall y \forall ...
2
votes
0answers
320 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
1
vote
0answers
31 views

Regarding the number of isomorphisms between splitting fields

Let $\phi : F \rightarrow F_1$ be an isomophism of fields and $f(x) > \in F[x]$. Let $\Phi : F[x] \rightarrow F_1[x]$ be the unique ring isomorphism which extends $\phi$ and maps $x$ to ...
1
vote
0answers
38 views

How do you express $\sum_{j=1}^{n} j^{k+1}$ in terms of $\sum_{j=1}^{n} j^{k}$?

I am trying to use induction to prove, for every positive integer $k$, that $$\sum_{j=1}^{n} {j^{k}} = \frac{n^{k+1}}{k+1} +\frac{n^k}{2} + P_{k-1}(n)$$ where $P_{k-1}$ is a polynomial of degree at ...
1
vote
0answers
42 views

Problem with induction of binomial coefficiency

(Sorry for making up math language, I am roughly translating math terms here) This is part of some of the induction exercises in the book "Otto Forster: Analysis 1" (1.2): ...
1
vote
0answers
37 views

How to correctly set up inductive proofs?

In practice, do you do some work on the inductive step and then reverse your steps? For example. Say you have this recurrence: $f(n+1) = 2f(n) + 1$ with $f(0) = 0$ This creates the sequence $0, 1, ...
1
vote
0answers
16 views

Establishing a proof through the structure of a term in predicate logic

Let $F$ be a ranked alphabet of function symbols. And let $X$ be an alphabet of variables. The set of terms $T$ , built over $F$ and $X$ , is inductively defined as follows: If $x\in X$, then ...
1
vote
0answers
21 views

Inductive proof of associativity of free groups

I'm really struggling with the inductive proof of the associativity of free groups, given about halfway down page 6 of this pdf. The bit I'm not getting is this: Suppose now that bc involves a ...
1
vote
0answers
29 views

Relation by induction

Suppose we have the element $a$ and $b$ in some algebra $A$ and $0<q<1$ subject to the relations: $$a^2b-(q+q^{-1})aba+ba^2=0$$ $$b^2a-(q+q^{-1})bab+ab^2=0$$ I want to deduce from this a ...
1
vote
0answers
33 views

Upper bound on a sequence after a finite number of steps

i need to find an upper bound (as tightest as possible) of the following recurrence for $\mu^{(j)}$ $$ \left\{ \begin{array}{l} t^{(j-1)} = 2 \mu^{(j-1)} - \nu & j \geq 1\\ \mu^{(j)} = ...
1
vote
0answers
69 views

Proof of the well ordering principle without mathematical induction

Is it possible to prove the well ordering principle without using mathematical induction? If yes, how?