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
85 views

Incomplete math induction

Making a proof for $n>7$ $$2^n>n^2+4n+5$$ Step 1 For $$n=7$$ $$2^7=128>7^2+4(7)+5=82$$ It is TRUE for $n=7$ Step 2 Inductive Hypotesis: It must be true for $n=k$ $$2^k>k^2+4k+5$$ ...
12
votes
2answers
454 views

Prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction.

Problem: prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction. I tried some, but stopped in $\sqrt[2^n]{n+1}$. Also tried with $2\sqrt{3\cdots}<3^2$ and so on.
2
votes
1answer
102 views

What is wrong with this induction?

Let $P(n)$ be any property pertaining to a natural number $n$. We will look this example: $$P(n) := (n = 0) \vee (n \leq -1) $$ Now, I will prove this and I'm asking that can you please show me where ...
2
votes
3answers
138 views

Prove by induction $\dfrac{n^n}{3^n}<n!<\dfrac{n^n}{2^n}$ [closed]

$\dfrac{n^n}{3^n}<n!<\dfrac{n^n}{2^n}$ The case $n!<\dfrac{n^n}{2^n}$ is easier.
43
votes
2answers
2k views

Proof of 1 = 0 by Mathematical Induction on Limits?

I got stuck with a problem that pop up in my mind while learning limits. I am still a high school student. Define $P(m)$ to be the statement: $\quad ...
2
votes
3answers
139 views

Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
1
vote
5answers
92 views

Show that by induction method that $2^{2^n}+1$ has $7$ in unit's place for all $n\geq 2$.

Show that by induction method that $2^{2^n}+1$ has $7$ in unit's place for all $n\geq 2$. I have tried to show this with the following way : Let $f(n)=2^{2^n}+1$. Then for ...
1
vote
1answer
67 views

Is this recursion well-defined?

I have a recursion defined by $$ f(n)=\max\{0,-c+pf(n-1)+(1-p)f(n+1)\} $$ with $0.5<p \leq 1$ and $f(0)=R>0$ and $f(m)=0$ for some $m>0$. I am trying to show that $f(n)$ is decreasing in ...
5
votes
2answers
863 views

Proving the AM:GM inequality

I am doing past exam papers preparing for the finals and I came across this questions about three times: Prove that: $$\frac{a_{1}+a_{2}+\cdots+a_{n}}{n}\geq \sqrt[n]{a_{1}.a_{2}...a_{n}}$$ ...
4
votes
2answers
3k views

Compute $1^2 + 3^2+ 5^2 + \cdots + (2n-1)^2$ by mathematical induction

I am doing mathematical induction. I am stuck with the question below. The left hand side is not getting equal to the right hand side. Please guide me how to do it further. $1^2 + 3^2+ 5^2 + ...
4
votes
3answers
456 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 ...
1
vote
2answers
45 views

Inductive proof of $\sum_{i=0}^{n} 2^{-i} \binom{n}{i} = \left(\frac{3}{2} \right)^n$

I am trying to prove by induction on $n$ the following theorem: $$\sum_{i=0}^{n} 2^{-i} \binom{n}{i} = \left(\frac{3}{2} \right)^n$$ For my inductive step I have: $$\sum_{i=0}^{n+1} 2^{-i} ...
1
vote
2answers
173 views

Why couldn't use the mathematical induction?

We can use mathematical induction which is deduced from Peano axioms and illustrated on Terence Tao's Real Analysis(here it is) Axiom 2.1 $0$ is a natural number. Axiom 2.2 If $n$ is a ...
2
votes
1answer
99 views

Prove that $C^n(\mathbb{R})$ is a subspace using induction.

Let $V$ be the set of all functions $f:\mathbb{R}\to\mathbb{R}$. Prove by induction that $C^n(\mathbb{R})$ is a subspace of $V$. I feel that this could be shown directly without much issue using the ...
2
votes
2answers
134 views

Proving an identity by induction

Can you help me prove the following identity or refer to a proof for it: $$ \sum_{n=0}^{\infty}x^{n}\left(\begin{array}{c} n+1\\ i \end{array}\right)=\frac{x^{i-1}}{(1-x)^{i+1}}, $$ for ...
10
votes
1answer
253 views

An inequality $\,\, (1+1/n)^n<3-1/n \,$using mathematical induction

It was shown in here that $\left(1+\frac{1}{n}\right)^n < n$ for $n>3$. I think we can be come up with a better bound, as follows: $$\left(1+\frac{1}{n}\right)^n \le 3-\frac{1}{n}$$ for ...
2
votes
3answers
618 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. ...
-1
votes
3answers
104 views

Prove that $n! \geq 2^{n-1}$ for $ n\geq1$ [duplicate]

Mathematical Induction:-Prove that $n! \geq 2^{(n-1)}$ for $n\geq 1$. I tried mathematical induction but could not
1
vote
6answers
113 views

Need help with a proof by induction (sum of an arithmetic progression)

Prove by induction that $(n+1)+(n+2)\cdots+2n=\frac{1}{2}n(3n+1)$ I was not really sure how to do this, but I assumed that the case holds for $n=k$, therefore ...
2
votes
3answers
99 views

Proving $\prod((k^2-1)/k^2)=(n+1)/(2n)$ by induction

$$P_n = \prod^n_{k=2} \left(\frac{k^2 - 1}{k^2}\right)$$ Someone already helped me see that $$P_n = \frac{1}{2}.\frac{n + 1}{n} $$ Now I have to prove, by induction, that the formula for $P_n$ is ...
1
vote
1answer
367 views

Math induction problem (rules of exponents)

Hello I am doing some induction problems, I have to prove that $3^{k+1}-1$ is a multiple of 2. Suddenly they make this statement; $3^{k+1}$ is also $3 * 3^k$. Why is that?
0
votes
2answers
592 views

Proof of sum of sinus terms with mathematical induction.

Hello dear community I have some issues in solving the following problem: Proposition: If $x$ is a real number not divisible by $\pi$ ($x\notin \pi\mathbb{Z}$), then for all integers $n \ge 1$ ...
2
votes
1answer
169 views

Mathematical induction supported by geometric interpretation

I need to demonstrate that: (a) $$1^2+2^2+3^2+\dots+n^2 = \frac{n(n+1)(2n+1)}6$$ using "mathematical induction". If I make some interpretation of the Peano's postulates then the way to demonstrate ...
0
votes
1answer
281 views

Prove that for all positive integers $n…$ [duplicate]

Prove that for all positive integers $n, 1^3+2^3+\ldots+n^3=(1+2+\ldots+n)^2$
0
votes
1answer
105 views

Proofs using wel ordering principle

Just recently , I came to knopw that mathematical induction and well ordering principle are eqivalent. b So, I'VE trying to solve this inductipn problem using WOP but haven't got anything useful ...
1
vote
1answer
46 views

Inductive demonstration

I have this: $$1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}6$$ So I was suggested of doing this: $$\begin{align} (1^2+2^2+3^2+\dots+k^2)+(k+1)^2 &= \frac{k(k+1)(2k+1)}6+(k+1)^2 \\ &= ...
1
vote
1answer
121 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
43 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
61 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
203 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
112 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
614 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
394 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
366 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 ...
5
votes
4answers
152 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 ...
0
votes
1answer
657 views

mathematical induction; recursive definition of the set of all positive integers; $7^{2n+1} + 6^{n+2}$ divisible by $43$

It says here: give a recursive definition of the set $P$ of all positive integers greater than $1$, whereby I'm not certain whether the answer is: Rule 1: $P$ is greater than $1$ Rule 2: If $x$ is ...
0
votes
2answers
101 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
111 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
283 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
167 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
372 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 ...
0
votes
0answers
67 views

Mathematical induction, equivalence of formulations, check my proof please.

I've starting going through Tao's Analysis I and in the first chapter there is an exercise about proving the equivalence of weak and strong induction. In the text, the principle of induction is an ...
2
votes
2answers
240 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
2answers
68 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)}$.
2
votes
3answers
518 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
242 views

Another hat problem

A finite number of prisoners, after being given their hats (black or white), are able to see one another but themselves, and then they are ordered to jot down their guess on the color of their own ...
1
vote
4answers
344 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 ...
19
votes
7answers
474 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 ...
2
votes
2answers
322 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 ...
2
votes
7answers
254 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 ...