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

learn more… | top users | synonyms

8
votes
0answers
299 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 ...
6
votes
0answers
184 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
5
votes
0answers
43 views

Show that $(1+a_1x+\ldots+a_rx^r)^k=1+x+x^{r+1}q(x)$

Fixed $k\ge 1$. Show that for each $r$, you can find $a_1,\cdot\cdot\cdot,a_r\in \mathbb{F}$ such that :$$(1+a_1x+\cdot\cdot\cdot+a_rx^r)^k=1+x+x^{r+1}q(x)$$ where $q(x)$ is a polynomial. Any ...
5
votes
0answers
150 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)$ ...
4
votes
0answers
58 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
81 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
167 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
113 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
35 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
44 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
57 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$) is ...
3
votes
0answers
82 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
73 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 ...
3
votes
0answers
483 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 ...
2
votes
0answers
40 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 ...
2
votes
0answers
51 views

Prove inequalities with induction

I have the following inequality to prove with induction: $$P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots\frac{1}{\sqrt{n}}>2-\frac{2}{n}, \forall n\in \mathbb{\:N}^*$$ I ...
2
votes
0answers
93 views

Prove, using the method of mathematical induction that the following holds true

For natural numbers $n\ge1$ show the following inequality using induction. $$n^{1/n}\le 1+\sqrt{\frac{2}{n}}$$
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
53 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
83 views

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

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

Homework Question for a 15 year old

My younger brother(age: 14 years 7 months) and his classmates were given a set of eight questions by his class-teacher, which included the following two questions: (i) Find, if you can, the fallacy ...
2
votes
0answers
105 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
82 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
98 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
44 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
139 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
58 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
89 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
68 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
192 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
238 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
51 views

can anyone prove this with induction?

Suppose that we have a sequence of numbers $x_1,x_2,\ldots,x_n$ called $S$. A subsequence of $S$ is a sequence obtained by omitting some elements of $S$. An increasing subsequence of $S$ called $IS$ ...
1
vote
0answers
49 views

Closed form of an equation

How could I find a closed form for the equations 1^3 = 1 , 2^3 = 3 + 5 , 3^3 = 7 + 9 + 11 , 4^3 = 13 + 15 + 17 + 19, 5^3 = 21 + 23 + 25 + 27 + 29 ... and Prove this closed form by induction? Thanks
1
vote
0answers
22 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
1
vote
0answers
13 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
1
vote
0answers
14 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
1
vote
0answers
32 views

Game of writing a binary sequence proof

Let $n \gt 2$ be a natural number. We consider the following game. Two players write a sequence of $0$s and $1$s. They start with an empty line and alternate their moves. In each move, a player writes ...
1
vote
0answers
32 views

Harmonic numbers, proof that h2^k >= 1+(k/2) with induction

I'm just starting with the concept of proving mathematical statements with induction. The complete exercise with solution can be found under: ...
1
vote
0answers
28 views

Prove that $10 | (n^a - n^b)$.

$n$ is a positive integer. Prove that there exists positive integers $a$ and $b$, $(a > b)$ such that $10 | (n^a - n^b)$. I have tried to prove this by induction on $n$, but I get stuck at the ...
1
vote
0answers
32 views

RE : Is greatest common divisor of two numbers really their smallest linear combination?

This is in reference to the same proof given in the post Is greatest common divisor of two numbers really their smallest linear combination? I couldn't add a comment there so I'm asking it here. I ...
1
vote
0answers
57 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
1
vote
0answers
48 views

Prove sequence with fibonacci recurrence bounded by $(7/4)^n$

Posting even though correct just for feedback, etc. $n_0,n_1$ are lower/upper bounds of true values for strong induction. Guess I could have used different values, like 2 and 3, or 1 and 2, but it ...
1
vote
0answers
40 views

Mathematical Induction - Can terms be split up individually?

My doubt is regarding a particular technique of solving recurrence relations. Say, we have T(n) = T(floor(2n/5)) + 4T(floor(n/8)) + cn I wonder if we can find the individual time complexities of ...
1
vote
0answers
42 views

Finding Function Representation of Recursive Sequence

I was trying to find one of the roots of $x^2 + 4x + 3 = 0$ by deriving a continued fraction from the recursive formula $x = -3/x - 4$ (every step of the approximation you increase the recursion by ...
1
vote
0answers
56 views

Prove The following geometrically

$1^3 + 2^3 + 3^3 .......... +n^3 = (\frac{n(n+1)}{2})^2$ How am I supposed to prove this geometrically? I am sure we have to consider 3 dimensional space. But cannot figure it out how. Help
1
vote
0answers
47 views

A sequence defined as $a(n)=n-a(a(n-1))$ $n\geq 1,\ a(0)=0$, how to prove that $a(n)=⌊(n+1)(-1+√5)/2⌋$

$a(n)=n-a(a(n-1)), \ n \geq 1,\ a(0)=0$, to prove that $$ a(n)=⌊(n+1)\cdot \frac{\sqrt{5} - 1}{2}⌋. $$ This is an exercise of "Discrete Mathematics and Its Application".(Supplementary exercise 72 of ...
1
vote
0answers
69 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
1
vote
0answers
43 views

Taylor's Approximation proof by induction

I'm really stuck on this question Let $f(x)$ be a function on $[a,b]$ which is $(n + 1)$ times differentiable at every point, for some natural number $n$. Let $c$ be a point in $(a,b)$. Using ...
1
vote
0answers
44 views

Use of mathematical induction to compute $\int_0^{\pi/2} \sin^{2n+1}xdx$?

We are given a reduction formula for $\int \sin^n xdx$, namely $$\int \sin^nxdx = -\frac{1}{n}\sin^{n-1}x\cos x + \frac{n-1}{n}\int \sin^{n-2}xdx.$$ I know how to derive this reduction formula. How ...
1
vote
0answers
162 views

Variation of Nim: Player who takes last match loses

Here is a homework problem I can't understand the solution to. Can anyone help me understand why they are using "mod 4"? Can someone help me understand this strong induction example? Thanks everyone! ...