Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

2
votes
2answers
344 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
748 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
78 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
546 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
555 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
2k 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
530 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
322 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
864 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
253 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
266 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
64 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
330 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
394 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
80 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
98 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
922 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
236 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
162 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
101 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
468 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
262 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
242 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
121 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
4k 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 ...
0
votes
1answer
301 views

How to find closed form by induction [duplicate]

How can I find the closed form of a) 1+3+5+...+(2n+1) b) 1^2 + 2^2 + ... + n^2 using induction? I'm new to this site, and I've thought about using the series 1 ...
3
votes
4answers
238 views

Use weak induction to prove the following statement is true for every positive integer $n$: $2+6+18+\dots+2\cdot 3^{n-1}=3^n-1$

Use weak induction to prove the following statement is true for every positive integer $n$: $$2+6+18+\dots+2\cdot 3^{n-1}=3^n-1$$ Base Step: Prove it is true for $n$. Inductive Hypothesis: It will be ...
2
votes
3answers
279 views

Show that the postage of six cents or more can be achieved by using only 2-cent and 7-cent stamps by using strong induction.

Show that the postage of six cents or more can be achieved by using only 2-cent and 7-cent stamps by using strong induction. I know the important step to keep in mind is: Induction step: If $P(m), ...
2
votes
2answers
203 views

Logic and Principle of Induction

I started studying about the mathematical principle of induction recently and i concluded that the mathematical principle of induction applied in some set N , to prove some property p for elements ...
1
vote
3answers
124 views

Proving $\sum_{k=1}^nk^3 = \left(\sum_{k=1}^n k\right)^2$ using complete induction [duplicate]

I tried to prove the following statement using complete induction but I couldn't manage to solve it because I got a complex notation eventually. The statement is the following: $$\sum_{k=1}^nk^3 = ...
4
votes
3answers
656 views

induction proof: $\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$

I encountered the following induction proof on a practice exam for calculus: $$\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$$ I have to prove this statement with induction. Can anyone please help me ...
2
votes
1answer
71 views

General term of a range

I started to solve a task and I did it. Tasks says:Find the currence formula of the range with these terms:$1,2,4,8 \dots$ I found it: $$X_1=1,X_{n+1}=1+X_1+X_2+\dots+X_n, n\ge1.$$ Now I'm trying to ...
0
votes
3answers
185 views

Show by induction that $n^3 \leq 3^n$ for all natural numbers n.

I need to show, using induction, that $n^3\leq 3^n$ for all natural numbers $n$. I tried the three steps to prove by induction putting $n=1$ then $n=k$ and at last I need the idea when I substitute ...
3
votes
5answers
144 views

How can I prove that $\sum\limits_{m=k}^{k+2n}\!\!\!m$ is divisible by $2n + 1$?

Show that $\sum\limits_{m=k}^{k+2n}\!\!\!m$ is divisible by $2n + 1$, where $n > 0$ and $k > 0$. I don't know how to go about this question, any help will be greatly appreciated.
5
votes
1answer
351 views

What is wrong with my induction proof?

The Fibonacci sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n \ge 2, a_{n+1} = a_n + a_{n-1}$. Thus the sequence begins $$1,1,2,3,5,8,13,21,...$$ prove that for all $n \ge 1, a_n < ...
5
votes
2answers
130 views

Proof by induction: one of $n, n+1,\ldots,2n$ is a square

Show that for every positive integer $n$, one of the numbers $n, n + 1, n + 2, \cdots , 2n$ is the square of an integer. here what i did. but I am doing some thing wrong here and iam not sure ...
3
votes
2answers
178 views

Proof using the Principle of Mathematical Induction

Use induction to prove that $n! > 3n$ for $n\ge4 $. I have done the base case and got both sides being equal to $24>12$ for $n=4$. However, when doing the inductive step I can't seem to ...
0
votes
2answers
145 views

Request for reference and technical support

I am going to write my master thesis in order to become a teacher of mathematics (with second subject business management). Supported by the ERASMUS program I have the opportunity to do this in ...
4
votes
2answers
1k views

Well-Ordering and Mathematical Induction

Here is my attempt to prove the Well-ordering principle, i.e. Any non-empty subset of $\Bbb N$, the set of natural numbers has a minimum element. Proof: Suppose there exists a non-empty subset $S$ of ...