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

1
vote
1answer
165 views

Prove correctness for this lcm iterative program

Studying for finals, trying to solve this problem: Given positive integers $n$ and $m$, we say that $m$ is a multiple of $n$ iff there is some $k \in N$ such that $m = kn$. For positive ...
1
vote
1answer
124 views

Why do sequences exist? What does “constructing a sequence” mean formally?

Everybody knows arguments like: "We can construct such a sequence inductively. Let $a_0$ be chosen as [..]. Then we can choose $a_{k+1}$ out of the set $A_{k+1}$ (which was shown to be non-empty)." ...
1
vote
1answer
44 views

Find the minimal $n\in \mathbb{N}$ that from this $n$ the inequality is true

I want to check with induction those inequalities and find the minimal $n\in \mathbb{N}$ that from him the inequality exists $3n-1<2^n$ $n^2+1<3^n$ $2n^3+1<4^n$ for (1.) its true only if I ...
3
votes
4answers
64 views

Prove with Induction for $n\in \mathbb{N}$ and $n$ is even for $1^2-3^2+5^2-7^2+\dots+(2n-3)^2-(2n-1)^2=-2n^2 $

I want to prove by indection, for $n\in\mathbb N$ even: $$1^2-3^2+5^2-7^2+\dots+(2n-3)^2-(2n-1)^2=-2n^2 $$ what I did first is to check the numbers, so if $n$ is even lets take $n=2$ so $(2\cdot ...
3
votes
6answers
220 views

Prove: $\frac{1}{1^2} +\frac{1}{2^2} + \cdots + \frac{1}{n^2} + \cdots = \sum_{n=1}^\infty \frac{1}{n^2} < 2$ [duplicate]

While I don't doubt that this question is covered somewhere else I can't seem to find it, or anything close enough to which I can springboard. I however am trying to prove $$\frac{1}{1^2} ...
1
vote
2answers
165 views

Proof of the principle of backwards induction

I have difficulty in neatly writing down a proof for the following: Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, ...
1
vote
1answer
1k views

Proof for Strong Induction Principle

I am currently studying analysis and I came across the following exercise. Proposotion 2.2.14 Let $m_0$ be a natural number and let $P(m)$ be a property pertaining to an arbitrary natural ...
1
vote
3answers
445 views

Summation and proof by induction question

I can't figure this out based on examples in textbooks, etc. Show via induction that $\sum_{j=1}^{n}j(j+1)(j+2)=\frac{n(n+1)(n+2)(n+3)}{4}$ So far, I have: (a) base case $P(1)= 1(1+1)(1+2) = ...
0
votes
2answers
608 views

How to proof linearity property of summations with induction

Recently I have faced with this question: $ {\sum_{k=1}^{n} (ca_k+ b_k) = c \sum_{k=1}^{n} a_k + \sum_{k=1}^{n} b_k }$ Proof linearity property of summations for all n ≥ 0 by using mathematical ...
0
votes
2answers
127 views

Backward induction (Tao Analysis vol. 1).

Exercise 2.2.6: Let $n$ be a natural number, and let $P(m)$ be a property pertaining to natural numbers such that whenever $P(m+1)$ is true, then $P(m)$ is also true. Suppose that also $P(n)$ is ...
1
vote
0answers
137 views

What is “Transitive induction”?

In the book "Artinian Modules Over Group Rings" By Leonid Kurdachenko, Javier Otal, Igor Ya Subbotin (also see http://books.google.com/) one can read (on p.117) "applying transitive induction, we ...
1
vote
2answers
456 views

How can it be proved that the geometric mean function is concave?

A function $f: \mathbb R ^n \rightarrow \mathbb R $ is said to be concave if $\forall x,y \in \mathbb{R}^n, \forall \lambda \in [0,1]$ we have $ \lambda f(x) + (1-\lambda)f(y) \le f( \lambda x + ...
2
votes
2answers
242 views

Finite Set Induction

Let A be a set and let $FS(A)$ be the set of all finite subsets of $A$. Then to prove a formula of the form $$(\forall S \in FS(A))(Q(S))$$ it is sufficiently to prove the following two formulae: ...
1
vote
1answer
516 views

Proving that a square can be divided into $n$ smaller squares for $n \ge 6$

I'm trying to prove that for all natural numbers $n \ge 6$, a square can be divided into $n$ smaller squares. The smaller squares do not need to be of the same size. So for induction, the base case ...
2
votes
2answers
361 views

Need help calculating this determinant using induction

This is the determinant of a matrix of ($n \times n$) that needs to be calculated: \begin{pmatrix} 3 &2 &0 &0 &\cdots &0 &0 &0 &0\\ 1 &3 &2 &0 &\cdots ...
2
votes
3answers
770 views

Strong inductive proof for this inequality using the Fibonacci sequence.

Problem I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to ...
2
votes
2answers
81 views

inductive proof of geometric series

I am stuck on understanding the inductive proof of geometric series. Specifically, I don't see how $ar^{k+1}$ equates to $\dfrac {(ar^{k+2}-ar^{k+1})}{(r-1)}$.
1
vote
4answers
576 views

How can I expand mathematical induction to rational numbers?

I know mathematical induction can be used to prove that a statements is true for all natural numbers (or those belonging to a certain subset of N). However, it is pretty obvious, unless I'm terribly ...
2
votes
2answers
604 views

Induction Proof for a series expansion of a function

I have done induction proofs of many different types, but trying to prove by induction that a derivative from the Taylor series expansion of a function has me stumped in terms of how to get the final ...
16
votes
12answers
3k views

Prove that $ n < 2^{n}$ for all natural numbers $n$.

Prove that $ n < 2^{n} $ for all natural numbers $n$. I tried this with induction: Inequality clearly holds when $n=1$. Supposing that when $n=k$, $k<2^{k}$. Considering $k+1 <2^{k}+1$, ...
21
votes
7answers
541 views

Illustrative examples of a phenomenon in the logic of mathematical induction

It is said (and I myself have said) that in some cases the easiest way to prove a statement by mathematical induction is to prove a stronger statement by mathematical induction, because then one has a ...
3
votes
5answers
325 views

What does “Prove by induction” mean?

What does "Prove by induction" mean ? I've heard it a lot! Would you mind giving me an example? Thanks
2
votes
4answers
930 views

For what natural numbers is $n^3 < 2^n$? Prove by induction

Problem For what natural numbers is $n^3 < 2^n$? Attempt @ Solution For $n=1$, $1 < 2$ Suppose $n^3 < 2^n$ for some $n = k \ge 1$ It looks like the inequality is true for $n = 0$, $n = 1$ ...
1
vote
1answer
103 views

Mathematical Induction — $a_n=2a_{n-1}-1$

Problem Finish the following mathematical induction showing that $a_0 = 2$ and $a_n = 2a_{n-1}-1$ implies $a_n = 2^n +1$. Basis: Prove that $a_0 = 2^0 + 1$ Proof: $a_0$ = $________$ = $________$ = ...
10
votes
4answers
256 views

Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove $$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$ I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. ...
2
votes
4answers
289 views

Induction for statements with more than one variable.

I'm going through the first chapters of Tao's Analysis text and I'm not entirely sure about one thing, namely why we're allowed to 'fix' variables when inductively proving statements pertaining to ...
1
vote
0answers
65 views

How do I Prove (by induction) that the series $1^3+2^3+…+n^3=(1+2+…+n)^2$? [duplicate]

This is a question from my textbook, it goes like this: Prove (by induction) that the series $1^3+2^3+...+n^3=(1+2+...+n)^2$ Here is my attempt at a solution: The base case would be: $n = 1 ...
5
votes
4answers
162 views

“Fixed $k$” in Mathematical Induction

On page 34, in his Calculus book, Apostol gives the following description of proof by induction: Method of proof by induction. Let $A(n)$ by an assertion involving an integer $n$. We conclude that ...
4
votes
1answer
2k views

Prove that at a party with at least two people, there are two people who know the same number of people…

Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full: "Prove that at a party ...
2
votes
8answers
336 views

Prove that $9\mid (4^n+15n-1)$ for all $n\in\mathbb N$

First of all I would like to thank you for all the help you've given me so far. Once again, I'm having some issues with a typical exam problem about divisibility. The problem says that: Prove ...
5
votes
2answers
405 views

Suggestions on how to prove the following equality. $a^{m+n}=a^m a^n$

Let $a$ be a nonzero number and $m$ and $n$ be integers. Prove the following equality: $a^{m+n}=a^{m}a^{n}$ I'm not really sure what direction to go in. I'm not sure if I need to show for $n$ ...
1
vote
1answer
82 views

Prove inequality by induction

Once again, I'm stuck in a demonstration by induction, this time, it's really proving that an inequality is valid. So, here is the inequality: Prove that $\binom{2n}{n} \geq (n+5)^2 \ \forall n ...
1
vote
2answers
62 views

Is this inequality property true?

I'm having some trouble defining weather this inequality is true or not... Basically, I wanted to know if its true that if $a \geq b$ and $c \geq d \Rightarrow a + c \geq b + d$ Well, basically ...
1
vote
6answers
99 views

Proof by induction that the sum of terms is integer

I'm having some trouble in order to solve this induction proof. Proof that $\forall{n} \in \mathbb{N}$ the number $\frac{1}{5}n^5+\frac{1}{3}n^3 + \frac{7}{15}n$ is an integer. I've tried ...
3
votes
3answers
945 views

For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. ...
3
votes
2answers
242 views

Inductive/Recursive definitions and Induction

I have known the principle of mathematical induction for a long time on set of natural numbers. Recently, i began reading mathematical logic books and learned about inductive and recursive definition ...
0
votes
1answer
74 views

Mathematical induction solution I don't understand

$$T(k) = 2T(\frac{k}{2})+k^2$$ $$T(k)\leq 2(c(\frac{k}{2})^2\log(\frac{k}{2}))+k^2$$ $$T(k)\leq \frac{ck^2\log\frac{k}{2}} { 2} + k^2$$ $$T(k)\leq \frac{ck^2logk}{2} - \frac{ck^2}{2} + k^2$$ ...
0
votes
1answer
60 views

Part of a solution to a mathematical induction problem I don't understand

There's a part in the solution that I can't understand, I think it's just something basic that I'm missing. In the solution it says: $$T(k) \leq 2(c(k/2)^2 \log(k/2)) + k^2$$ Then it became $$T(k) ...
1
vote
4answers
76 views

Induction of inequality involving AP

Prove by induction that $$(a_{1}+a_{2}+\cdots+a_{n})\left(\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}\right)\geq n^{2}$$ where $n$ is a positive integer and $a_1, a_2,\dots, a_n$ are real ...
0
votes
1answer
1k views

Show that the product of upper triangular matrices is upper triangular

I have a question. Prove that the product of an [arbitrary] number of upper triangular matrices of [arbitrary] size with [undetermined] upper triangular entries is upper triangular using induction? ...
1
vote
1answer
60 views

Flavius Josephus: $J(2^i)=1~\forall i\geq 1$ (An Inductive Proof)

I'm asked to "[u]se induction to show that $J(2^i)=1$ for all $i\geq 1$. Where do I start? Here $J(n)$ is the last position of $n$ baskets with balls in them for which every second basket, starting ...
1
vote
2answers
165 views

Induction proof, help please?

I have a problem that I need to prove using induction. Prove that a surjective function has at least as many members in its domain as it does in its codomain. Do I begin by using the axiom of choice? ...
4
votes
1answer
105 views

Prove $2^n > n^3$ for all $n \ge10$ [duplicate]

I am stuck with the this question: Prove by induction that $2^n > n^3$, for all $n \ge 10$ I got this far: Base: For $P(10)$: $$ 2^n > n^3 \\ 2^{10} > 10^3 \\ 1024 > 1000 $$ so, ...
0
votes
1answer
488 views

Question on induction-1 is the least positive integer

Question on induction prove: 1 is the least positive integer. proof: Let $A=\left\{x\geq 1\left|x\in Z^+\right.\right\}$, and then $1\in A$, if positive integer $n\in A$, then $n\geq 1$, Since ...
4
votes
3answers
275 views

An odd question about induction.

Given $n$ $0$'s and $n$ $1$'s distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to ...
0
votes
1answer
254 views

$n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines ...
0
votes
0answers
125 views

Induction proof of surjectivity

I have a problem. Let $A: S\to T$ be a surjective map between finite sets. Prove by induction that $|S|\geq|T|$ and that if $|S|=|T|$, then $A$ is bijective. Another way to phrase the question is: ...
1
vote
3answers
135 views

Using complete induction, prove that if $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$, then $a_n=2^n$

Could anyone please explain to me how to do this problem by using the principle of complete induction? Thanks. :) Let $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$ for all $n\geq 1$. Prove that ...
0
votes
2answers
69 views

Prove by induction: $\forall n\in\mathbb{Z}_{\geq1}:3\ |\ (6n^2-12n+3)$

I'm not sure how to start this induction problem. I was told that we start doing induction by using a base case $n=1$. Then we set $n=k$ to prove $n=k+1$. But how do I prove that ...
5
votes
6answers
5k views

Proving by induction: $2^n > n^3 $ for any natural number $n > 9$ [duplicate]

I need to prove that $$ 2^n > n^3\quad \forall n\in \mathbb N, \;n>9.$$ Now that is actually very easy if we prove it for real numbers using calculus. But I need a proof that uses mathematical ...