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

0
votes
1answer
61 views

strong induction example

There is following example given in a book. I am not sure how do we conclude that $a$ is divisible by prime? See this section: Case 2 ($k + 1$ is not prime): In this case $k+1=ab$ where $a$ and ...
3
votes
3answers
100 views

${n \choose k}\leq n^k$

Let $n$ et $k\in \mathbb{N}$ such that : $k\leq n $ Show that :$${n \choose k}\leq n^{k}$$ My thoughts: note that for all $\ k\leq n$ : $${n \choose k}=\frac{n!}{k!(n-k)!}$$ To prove ...
1
vote
2answers
28 views

Prove by induction that $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$

Prove by induction $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$ Step 1: Show true for n = 0: LHS: $\frac{0}{2^{0}}$ = 0 RHS = $2 - ...
1
vote
1answer
26 views

Prove by induction that $\sum_{k=0}^{n}(-1)^{n+k} k^{2} = \frac{n(n+1)}{2}$

Prove by mathematical induction that $\forall n \in \mathbb{N}:~~~~ \sum_{k=0}^{n}(-1)^{n+k} k^{2} = \frac{n(n+1)}{2}$ Step 1: Show true for $n = 1$: LHS: $(-1)^{(1+0)} \cdot 0^{2} + (-1)^{(1+1)} ...
1
vote
2answers
51 views

Simplify sum of factorials with mathematical induction

I want to prove with mathematical induction that: $$\sum_{i=1}^n i \cdot i! = (n+1)! - 1$$ So in the first step we define $n = 1$: $$\sum_{i=1}^1 i \cdot i! = 1 \cdot 1! = 1 = 2! - 1$$ In the ...
1
vote
3answers
45 views

Prove that if a set A of natural numbers contains $n_0$ and whenever A contains k it also contains k+1.

Prove that if a set A of natural numbers contains $n_0$ and that whenever A contains k it also contains k+1. Prove that A contains all natural numbers $ \geq n_0 $ This is rather similar to a ...
0
votes
1answer
44 views

Prove Bernoulli inequality if $h>-1$

Qi) Prove Bernoulli's inequality If $h> -1$, then $ (1+h)^n \geq 1+nh$ Qii) why is this Trivial is $h>0 $ Something i have always been lucky with is having a lot of intuition to go on with ...
0
votes
1answer
30 views

Is this inductive proof valid?

Show that $n!>3^n$ for $n \ge 7$ My attempt: Let the statement $P_n$ say that $n!>3^n$. Base Case Let $n=7$, then $P_7$ says that $7! > 3^7 \implies 5040>2187$ Inductive Step Fix $k ...
1
vote
1answer
44 views

induction, recursive function, discrete mathematics

Please help solve following recursive function. How can I solve $n-10$ for $M(99)$ or $M(98)$ if $n>100$ ? : Find $M(99), M(100)$, and $M(98)$ when $$ M(n) = \begin{cases} n-10, & ...
1
vote
1answer
50 views

Write $(1^3 −1)−(2^3 −1)+(3^3 −1)−(4^3 −1)+(5^3 −1)$ using summation or product notation.

Question: Write the following using summation or product notation: $$(1^3 −1)−(2^3 −1)+(3^3 −1)−(4^3 −1)+(5^3 −1)$$ I have got following conversion, however it looks a bit over complicated: ...
3
votes
3answers
52 views

How to prove $\sum_{k=1}^{n}k\binom{n}{k} = n2^{n-1}$ [duplicate]

$\sum_{k=1}^{n}k\binom{n}{k} = n2^{n-1}$ I have tried both induction and transforming both sides to get equality but no luck I know that $\sum_{k=1}^{n}\binom{n}{k} = 2^{n}-1$ and ...
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 ...
1
vote
1answer
62 views

Strong induction. What is responsible for basis step?

I have no problems with weak induction. There is a basis step and inductive step. But it seems that basis step is missing in the strong induction. It says that$$(\forall n[ \forall m<n, ...
2
votes
0answers
41 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 ...
5
votes
3answers
153 views

Proving inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + … + + \frac{1}{2^{n}-1} < n$

Prove the inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + ... + + \frac{1}{2^{n}-1} < n$ where $n\in\mathbb{N}\backslash\{0,1\}$ My work At first I tried ...
0
votes
0answers
41 views

Induction: Fibonacci / Lucas Numbers [duplicate]

From Andrews' Number Theory, Chapter 1, Section 1, Problem 15: Prove, by induction, that $F_{2n} = F_nL_n$ where $F_n$ denotes the nth Fibonacci number and $L_n$ denotes the nth Lucas ...
0
votes
1answer
43 views

Proving that $\sum_{i=0}^{n-p} \frac{i!}{(p+i)!} = \frac{1}{p-1}[\frac{1}{(p-1)!}-\frac{(n-p+1)!}{n!}]$

I'm trying to prove that $$\sum_{i=0}^{n-p} \frac{i!}{(p+i)!} = \frac{1}{p-1}\left[\frac{1}{(p-1)!}-\frac{(n-p+1)!}{n!}\right]$$ for $p,n \geq 2$, $p, q \in \mathbb{N}$. I'm trying to use induction ...
0
votes
1answer
85 views

Cauchy convergence criterion for the sequence $x_{n+1}=\frac{x_n+x_{n-1}}{2}$ [closed]

Suppose $x_0$, $x_1$ are arbitrary and a sequence $(x_n)$ be defined by $x_{n+1}=\frac{x_n+x_{n-1}}{2}, n\geq 1.$ I want show, by induction, the following: $x_0\leq x_n\leq x_1,\forall n\geq 1$; ...
23
votes
4answers
1k views

Why is “mathematical induction” called “mathematical”?

One of my whims is that I never write "mathematical induction" but just "induction". We are doing maths, so what is the point about precising? We don't say "Let $f$ be a mathematical function from the ...
2
votes
2answers
60 views

Understanding the proof that the sum of the first $n$ natural numbers is $\frac{1}{2}n(n+1)$ [duplicate]

I'm reading the following book: http://www.cs.princeton.edu/courses/archive/spring10/cos433/mathcs.pdf. In page 26, they attempt to prove the following theorem using Induction: For all $n \in ...
4
votes
3answers
202 views

Inequality of the Fibonacci sequence and the golden ratio

How can I prove that for each $n\in\Bbb Z^+$ $$\frac{f_{2n}}{f_{2n-1}}\leq\frac{1+\sqrt{5}}{2}$$ where each $f_i$ is a term of the Fibonacci sequence. Any help is really appreciated
1
vote
3answers
68 views

Induction on nth polynomial proof.

Question: Prove by induction that $ 1+r+r^2+\cdots+r^n = \dfrac {1-r^{n+1}} {1-r} $ where $ r \in \mathbb{R} $ When $n$ is odd, this is really easy as the right side breaks down to $\dfrac ...
2
votes
3answers
57 views

Tips on constructing a proof by induction.

So right now I'm working on a discrete mathematics course and I've been having a bit of trouble figuring out how to prove certain equations using mathematical induction. I have very little trouble ...
0
votes
4answers
118 views

How to prove that the sum of squared binomials equals $\binom{2n}{n}$ [duplicate]

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem ...
0
votes
3answers
82 views

Induction proof that $2^m 2^n = 2^{m+n}$

I am unable to proceed with the below claim. $$2^{m} \times 2^{n} = 2^{m+n}$$ Could anyone let me know how to prove the above claim using induction proof? I was able to derive proof for odd natural ...
1
vote
1answer
34 views

Question around the following relation: $T(n,1) = n$, for a positive integer $n$, and for all $k\geq 1,\ T(n,k+1)=n^{T(n,k)}$.

I'm beginning the studies on number theory and then i'm facing the following problem that i couldn't solve yet: given a positive integer $n$ and being $T(n,1)=n$ and, for all $k\ge1$, ...
0
votes
1answer
46 views

How to prove that $(a+b-ab)^n+(1-a^n)(1-b^n) \geq n $ for $a,b\in [0,1]$ and $n\in\mathbb{N}$?

Let $a,b\in [0,1]$ and $n\in\mathbb{N}$. Prove the following inequality: $$(a+b-ab)^n+(1-a^n)(1-b^n) \geq n $$ I thought on using M Induction: Assuming that the inequality holds for $n=k,$ ...
0
votes
2answers
52 views

A simple mathematical induction proof.

Let n be a natural number, and let $ f:\{ i \in \mathbb{N} : 1 \le i \le n\} \rightarrow\mathbb{N} $ be a function. Show that there exists a natural number M such that $f(i) \le M $ for $1 \le i \le ...
1
vote
4answers
59 views

How to prove this equation by induction?

I am trying to prove this equation by mathematical induction $$f_{n+1}f_{n-1} = f_{n}^{2}+(-1)^n$$ is true where $f_{n} = $ the nth number in the Fibonacci sequence. I don't quite get how to do this ...
1
vote
3answers
77 views

Want to ensure my proof is rigourous enough.

Question. Prove: $ 0 \leq x < y $ then $ x^n < y^n$ $ \forall n \in \mathbb{N} $ I'm particularly bad at proving obvious things but here it goes. ( please be super strict on analyzing my proof ...
1
vote
1answer
59 views

Induction and basic assumptions in Graph Theory

I am beginning to work through a text in graph theory and have a couple of questions. 1) Can we always assume a graph is nonempty, i.e., if a graph $G$ has order $n$, do we assume $n\in \{1,2,...\}$? ...
3
votes
1answer
59 views

Writing a proof of the convergence of a series defined recursively

Define the sequence $a_n$ recursively by $a_1=1$ and $$a_{n+1}=\frac13\left(a_n^2+\frac1n\right)$$ (a) Prove, by induction or otherwise, that $(a_n)$ is decreasing. (b) Prove that the series ...
1
vote
2answers
41 views

Prove the inequality $(n+1)^4 < 4n^4$ for $n\geq 3$ by induction

The inequality I'm concerned with is $(n+1)^4 < 4n^4,\ n\geq 3$. I'm not sure how induction is supposed to work here. If I assume $(k+1)^4<4k^4$, I cannot see how this helps show ...
1
vote
3answers
86 views

Factorial inequality $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n$ using induction

I want to show $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n.$ Assume that it holds for some positive integer $k\geq 1$ and we will prove, $2!\,4!\,6!\cdots (2k+2)!\geq\left((k+2)!\right)^{k+1}$. ...
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 ...
4
votes
6answers
424 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
1
vote
2answers
112 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$ \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} $$ The answer given (Knuth's book, The Art of ...
3
votes
1answer
48 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
3
votes
2answers
50 views

Proving that a function is absolutely monotonic on a given interval

According to the following Wolfram Alpha article: http://mathworld.wolfram.com/AbsolutelyMonotonicFunction.html, the function $f(x) = -\ln(-x)$ is absolutely monotonic on the interval $[-1,0)$. My ...
0
votes
2answers
33 views

Induction proof for $x \le y $

So these are $x \in \{1 ... i\}$ and $y \in \{ i + 1 ... n\}$, for $i, n \in \mathbb N$. I want to prove it for every $x \le y $. I know it`s easy but the solution is escaping me. I have tried with ...
1
vote
1answer
77 views

Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed. Progress Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1 $ ...
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$ ...
3
votes
1answer
52 views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...
0
votes
4answers
50 views

How to prove the sequence given by $a_{n+1}=s+a_n^2$ is monotonic increasing?

Let $s$ be $0\:\le \:s\le \:\frac{1}{4}$ and consider this sequence: $a_1\:=\:s$ $a_{n+1}\:=\:s\:+\:a_n^2$ I want to prove that is monotonic sequence, so I thought about induction or assume in ...
1
vote
4answers
87 views

Prove or disprove $n^2+41n+41$ is a prime number for every integer $n$

Prove or disprove $n^2+41n+41$ is a prime number for every integer $n$ I started with the base step: $n(0) = 0^2+41(0)+41 = 41$ But I have no idea how to proceed in proving this. Any tips or ...
1
vote
3answers
74 views

Prove that $1+2^1+2^2+\ldots +2^n=2^{n+1}-1$ using induction

For all integers $n\ge 1$ prove the following statement using mathematical induction. $$1+2^1+2^2+\ldots +2^n=2^{n+1}-1$$ The first part of the question ask me to prove the base step: So I set ...
0
votes
2answers
57 views

Mathematical induction help, please.

Use the second principle of mathematical induction to show that if f(1) is specified and a rule for finding f(n+1) from the values of f at the first n positive integers is given. Then f(n) is uniquely ...
1
vote
3answers
39 views

Compare inequalities in a proof by induction

I am solving a proof by induction example. But I ended up with my hypothesis $$ a_{n-1} \geq \frac{2^n}{2}+n^2-2n+1 $$ and my inductive step $$ a_{n-1} \geq \frac{2^n}{2}+\frac{n^2}{2}-\frac{n}{2}. ...
11
votes
7answers
953 views

Prove by induction that an expression is divisible by 11

Prove, by induction that $2^{3n-1}+5\cdot3^n$ is divisible by $11$ for any even number $n\in\Bbb N$. I am rather confused by this question. This is my attempt so far: For $n = 2$ $2^5 ...
0
votes
1answer
28 views

Can you use proof by contradiction inside simple induction?

During a proof using simple induction, I assumed P(k) is true. Now in order to show P(k+1) is true using P(k), can I do a proof by contradiction on P(k+1) and say P(k) would be wrong if P(k+1) is ...