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 ...
2
votes
1answer
27 views
what is ascending and descending induction?
On page 88 of Lang's "Topics in Cohomology of Groups", Lang mentions a technique he calls "ascending and descending induction".
Initially I felt a bit embarrassed that I did not know a sort of ...
5
votes
4answers
64 views
Prove that $3^n>n^4$ if $n\geq8$
Proving that $3^n>n^4$ if $n\geq8$
I tried mathematical induction start from $n=8$ as the base case, but I'm stuck when I have to use the fact that the statement is true for $n=k$ to prove ...
2
votes
1answer
47 views
Prove that $n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}$.
Let $c \not= 1$ be a real positive number, and let $n$ be a positive integer.
Prove that $$n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}.$$
My initial thought was to try and induct on $n$, but the ...
0
votes
2answers
58 views
How to prove this inequality by using induction?
If $x,y$ are distinct real numbers such that $x+y>0$ and $n\ge 1$, then $2^{n-1}(x^n+y^n)\ge (x+y)^n$.
It is obvious for $n=1$. How to do the rest by using induction?
1
vote
1answer
46 views
Combinatorics identity sum of
Prove that:
$$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$
By using only combinatorics identities.
1
vote
3answers
99 views
prove: $\dfrac{2^{n+1}+(-1)^n}{3}$
I am asked to prove this notation with induction for $n\in \mathbb{N}$:
real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as ...
0
votes
1answer
69 views
Improper integral $\int_{0}^{\infty}\frac{x^n}{x^{m+n+1}} \ dx=\frac{n! {(m-1)}!}{(m+n)!}.$
How can I prove that
$$\int_{0}^{\infty}\frac{x^n}{x^{m+n+1}} \ dx=\frac{n! {(m-1)}!}{(m+n)!}\quad ?$$
I tried to do induction on $n$ and on $m$, separately, but I could only do the base case ($n=1$ ...
2
votes
1answer
62 views
How to use induction to prove this argument?
It is obvious that this grammar will always return an equal number of both a's and b's. But I was wondering how to prove it using induction? I understand induction, but I was finding it hard to ...
2
votes
1answer
49 views
show by induction if there exists a $n_0 \in \mathbb N $such that $n\geq n_0 , n! \gt 2n^3$
I tried and I got there doesn't exist such a $n_0$
However, I dun think I have a formal proof for this.
My approach is, First assume there is such a $n_o$ exist
and start my calculation with ...
5
votes
3answers
106 views
Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]
The problem is following, prove that:
$$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$
I've tried solving this problem using mathematical induction, but I ...
2
votes
2answers
34 views
proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3
I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers:
$$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
0
votes
1answer
19 views
Recursive Definitions with Converse
I think I know how to solve i. and ii., but not iii:
Base Case: $(0,0) \in S$
Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$.
(For i and ii): Prove that if $(a,b) \in ...
2
votes
1answer
145 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 ...
0
votes
2answers
50 views
Prove summation using induction [duplicate]
$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$
My basis step is $P(1)$ sets the $LHS = RHS = 1$.
For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$:
...
0
votes
2answers
66 views
I need help with proofs using mathematical Induction
I need help with this problem: $2+7+12+17+...+(5n-3)=(\frac{n}{2})(5n-1)$
1
vote
1answer
27 views
Induction with compositions
Proposition. Suppose $g,h:\mathbb{R}\rightarrow\mathbb{R}, (g\circ h\circ g^{-1})^{n}=g\circ h^{n}\circ g^{-1}$ where $n\in\mathbb{N}$ and $g$ is a bijection.
We will prove this by mathematical ...
9
votes
2answers
369 views
9 pirates have to divide 1000 coins…
A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins.
Arriving on a deserted island, they now have to split up the ...
3
votes
4answers
81 views
Induction proof: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer.
Prove using induction: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer.
I tried but I can't do it.
1
vote
2answers
39 views
Induction on the Fibonacci sequence?
Prove by induction that the $i$th Fibonacci number satisfies the equality:
$$F_i = \frac {\phi^i - \hat\phi{}^i}{\sqrt5}$$
where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate.
...
6
votes
10answers
737 views
Prove by mathematical induction that $1 + 1/4 +\ldots + 1/4^n \to 4/3$
Please help. I haven't found any text on how to prove by induction this sort of problem:
$$
\lim_{n\to +\infty}1 + \frac{1}{4} + \frac{1}{4^2} + \cdots+ \frac{1}{4^n} = \frac{4}{3}
$$
I can't ...
7
votes
2answers
71 views
Fiboncacci theorem: Proof by induction
I have the following theorem to prove by induction:
$$
F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$
It is mentioned in my script that the proof should be possible only by using the ...
4
votes
4answers
112 views
If $S_n = 1+ 2 +3 + \cdots + n$, then prove that the last digit of $S_n$ is not 2,4 7,9.
If $S_n = 1 + 2 + 3 + \cdots + n,$ then prove that the last digit of $S_n$ cannot be 2, 4, 7, or 9 for any whole number n.
What I have done:
*I have determined that it is supposed to be done with ...
3
votes
1answer
38 views
Proving that $n|m\implies f_n|f_m$
Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$.
I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction ...
6
votes
2answers
114 views
Does this require transfinite induction?
Given any uncountable set S, would I need to use transfinite induction to prove if I remove single elements recursively, I will be left with the empty set?
It seems like this can be thought of as an ...
2
votes
1answer
52 views
Prove $\sin((2n+1)x)$ function by induction
Can someone help me prove the following by mathematical induction:
$$\sin((2n+1)x)=\sin(x)(1+2 \sum_{k=1}^{n} \cos(2kx))$$
I was told to use induction on $n$; however I keep getting stuck. Any help ...
1
vote
1answer
44 views
Proof by Induction solution not understood
Here is a question and solution but I don't understand what's happening after $m = m+1$.
How does $(3(m+1))!$ equal $(3m)!(3m+1)(3m+2)(3m+3)$? Should it not be $(3m+3)!$?
Same thing with the ...
2
votes
3answers
105 views
combinatorial argument and by induction proof
Let n be a fixed natural number. Show that:
$$\sum_{r=0}^m \binom {n+r-1}r = \binom {n+m}{m}$$
(A): using a combinatorial argument and (B): by induction on $m$?
-1
votes
0answers
40 views
Induction proof of $\frac{a_k}{a_n} \le \left(\frac12\right)^{k-n}$ for $a_k = \frac {x^k}{k!}, n \ge 1, k \ge n$
Let $a_k = \dfrac {x^k}{k!}, n \ge 1, k \ge n$.
Prove by induction that $\dfrac{a_k}{a_n} \le \left(\dfrac12\right)^{k-n}$.
I'm getting confused with the inequalities here.
6
votes
4answers
142 views
Mathematics Induction
Question:
Prove by mathematical induction that $$(1)+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)=\frac{1}{6}n(n+1)(n+2)$$ is true for all positive integers n.
Attempt:
I did the the induction steps and I ...
0
votes
1answer
26 views
Bernoulli's inequality (alternate form)
Prove through mathematical induction
$$
(1-x)^n≥1-nx$$ for $x<1,n≥1$
1
vote
1answer
63 views
Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$?
I have question
Q
Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$?
by using induction
Thanks
2
votes
2answers
52 views
Is mathematical induction necessary in this situation?
I was reading "Number Theory" by George E. Andrews.
On P.17, where he proves that for each pair of positive integers a,b, gcd(a,b) uniquely exists, I came up with a question.
The approach he used ...
1
vote
2answers
48 views
How can be done by the method of mathematical induction?
We are given that $P(x+1)-P(x)=2x+1$
We also know that $P(0)=1$
We want to prove that $P(2004)=(2004)^2 +1$
Can someone explain how can be solved with mathematical induction?
Thank you in advance!
0
votes
3answers
59 views
How can I use induction solve this?
How can I show/solve this? I've tried by using the basis step and the inductive step, but just can't seem to get it right.
$$\forall(n \geq 0)(4\mid(9^n − 5^n)).$$
1
vote
1answer
77 views
How to show by induction that, for $0<\theta<\pi$, $\det A_n=\frac{\sin (n+1)\theta}{\sin \theta}.$
I need help with the underlined part.
Thanks in advance
Let $A_n$ be the $n\times n$ matrix given by
$$a_{ij}=
\begin{cases}
0 & \text{if }|i-j|>1, \\
1 & \text{if }|i-j|=1, ...
0
votes
0answers
56 views
Simple proof of well ordering principle
I've seen some proof of the well-ordering principle and they all use the contradiction method.
However, direct proof would be simpler.
Can you check for my proof?
I will use mathematical ...
2
votes
2answers
37 views
Strong Mathematical Induction $3|b_n$
Here is what I have so far:
Proof $3|b_n$ for $n$ integers $\geq 1$
Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$
$P(1)=3|b_1$
$P(1)= 3|3$
Since $3|3$, the base case is true ...
1
vote
0answers
48 views
Mathematical induction
So the question was basically "
Suppose that there are n teams in a rugby league competition. Every team A
plays every other team B twice, once at the home ground for team A, and the other time
at the ...
1
vote
1answer
47 views
Generalized Josephus problem
I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as
f(1) = a
f(2n) = 2f(n) + b, for n >= 1
f(2n+1) = 2f(n) + y, for n >= 1
...
2
votes
4answers
43 views
mathematical induction
Suppose that $x > 0$ and let $n \geq 2$ be a positive integer. Prove that $(1 + x)^n \geq 1 + nx + \frac{n(n-1)}{2}x^2$
So for the base case, I have $x=1$, but that really is not getting me ...
0
votes
1answer
41 views
Question on the use of induction in the Electronic Mail Game
In Rubinstein's Electronic Mail Game, Player I and Player II's strategies take the form as $s_i : \mathbb{N} \to \{A,B\}$, $(i =1,2)$.
Rubinstein shows that the pair of constant functions, $s_1(t_1) ...
2
votes
3answers
68 views
Prove By Mathematical Induction
Prove $(n!)^{4}\le2^{n(n+1)}$ for $n = 0, 1, 2, 3,...$
Base Step: $(0!)^{4} = 1 \le 2^{0(0+1)} = 1$
IH: Assume that $(k!)^{4} \le 2^{k(k+1)}$ for some $k\in\mathbb N$.
Induction Step: Show ...
4
votes
1answer
50 views
Proving Inequality using Induction $a^n-b^n \leq na^{n-1}(a-b)$
I was trying to prove this inequality using induction, but couldn't do.
Question: Suppose $a$ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then:
...
12
votes
1answer
215 views
Prove $\sin(1/n)<1/n$ for all $n$
I need to prove $\sin(1/n)<1/n$ for all $n \in \Bbb N$ using mathematical induction.
Dont know how to start. Please help!
1
vote
1answer
46 views
How to prove that $n^k = O(2^n)$
I'm having issues trying to prove this.
The Big Oh definition is: f(n) = O(g(n)) if exists a real constant $c > 0$ and $n_0 \in \Bbb N $ in such a way that for all $n \ge n_0$ we have f(n) $\le$ ...
6
votes
4answers
287 views
$f: \mathbb{R} \to \mathbb{R}$ satisfies $(x-2)f(x)-(x+1)f(x-1) = 3$. Evaluate $f(2013)$, given that $f(2)=5$
The function $f : \mathbb{R} \to \mathbb{R}$ satisfies $(x-2)f(x)-(x+1)f(x-1) = 3$. Evaluate $f(2013)$, given that $f(2) = 5$.
0
votes
2answers
88 views
Flawed proof that all positive integers are equal
Suppose that we are trying to prove that for every positive integer n, if x and y are positive integers with max(x, y) = n, then x = y. For the base case, we suppose n = 1. If max(x, y) = 1 and x and ...
1
vote
1answer
42 views
Recursive algorithm correctness: problem.
Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
1
vote
2answers
106 views
A one-to-one function from a finite set to itself is onto - how to prove by induction?
I'm not sure if I can do this without knowing what f actually is?
Let $X$ be a finite set with $n$ elements and $f: X \rightarrow X$ a one-to-one function. Prove by induction that $f$ is an onto ...
5
votes
3answers
146 views
Prove the following using induction on n (matrices)
Prove the following using induction on n:
$$\begin{pmatrix} 2 & 1 \\ -1 & 0 \end{pmatrix}^{n} = \begin{pmatrix} n+1 & n \\ -n & -n+1 \end{pmatrix}$$
I know that multiplication of ...
