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

3
votes
2answers
289 views

Induction: show that $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + … + \frac{1}{\sqrt{n}} < 2\sqrt{n}$

The question: Induction: show that: $$1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$$ for $n \geq 1$ My attempt at a solution: First ...
3
votes
2answers
334 views

Fallacious Induction Proof that All Integers are Equal [duplicate]

We're currently learning about induction in my real analysis course. I came up with the following proof that is obviously false but cannot quite figure out why it fails. Here it is... "Any set $S$ of ...
0
votes
1answer
20 views

Conjecture based on limited trail followed by inductive proof

My syllabus says: recognise situations where conjecture based on a limited trail followed by inductive proof is a useful strategy, and carry this out in simple casses e.g. find the nth derivative ...
1
vote
1answer
132 views

Integration using induction question

Assume $f : [0, 1] \to \mathbb{R}$ is continuous and arbitrarily often differentiable on $(0, 1)$ (i.e. $f$ is smooth). Denote by $f^{m}$ the $m\text{-th}$ derivative of $f$ with $m∈\mathbb{N}$ and ...
1
vote
0answers
47 views

Proving the base case for a problem in elementary number theory

I have a question about how to prove statements such as the following, using induction: If $p \mid a_1a_2 \cdots a_k$, then $p \mid a_i$ for some $i$, $i = 1, 2, \ldots, k$, where $p$ is prime. ...
3
votes
2answers
109 views

Proving that $xy = yx$ where $x$ and $y$ are both strings.

I am to prove that the following holds for any two strings $x, y \in \lbrace 0, 1\rbrace^*$ $xy = yx$ if and only if $\exists z \in \{0,1\}^*$ and $i,j \in \mathbb N$, such that $x = z^i$ and $y = ...
1
vote
4answers
297 views

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number n. $0 \notin N$ Base Case: n = 2, since it is the first even natural number. $10^2 -1 = 99$ which is divisible by ...
0
votes
1answer
50 views

Prove the following inequality using induction: $(1 + \epsilon)^n \leq 1+ (2^n - 1)\epsilon$ for every $n \geq 1$ and $0 \leq \epsilon \leq 1$

Prove the following inequality using induction: $$(1 + \epsilon)^n \leq 1+ (2^n - 1)\epsilon$$ for every $n \in \mathbb{N}: n \geq 1$ and $0 \leq \epsilon \leq 1$ I'm familiar with the concept of ...
1
vote
2answers
106 views

How do I go about algebraic manipulation of polynomials with many terms?

I'm doing an inductive proof for a homework problem, and for one step, I need to show that $$ \dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30} + (n+1)^4 = \\ ...
4
votes
4answers
73 views

Proving a relation with induction

I have a problem: Let $p_n$ be the $n:th$ prime number ($p_1=2, p_2=3, p_3=5$ and so on). With induction, show that $p_{n+2}>3n$ for each integer $n\geq1$. I can't figure this out because the ...
4
votes
1answer
181 views

Prove by induction $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$

Anyone knows how to do this? I'm having trouble after the following step: Prove by induction that $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$ Thanks $((n(n+1)(n+2)(n+3))/4) + (n+1)(n+2)(n+3)$ ...
2
votes
2answers
729 views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
0
votes
1answer
42 views

Difficulties with mathematical induction?

I understand the concept of mathematical induction. Its towards the end where i feel that im missing something. Problem: Prove that $4^n=(4(4^n-16))/3$ for $n\le 3$. I have that the base case is ...
1
vote
1answer
53 views

Am I understanding induction correctly?

Here is an induction proof that I have written for my homework and I want to know if I am understanding this correctly: Prove that for: $ \sum\limits_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ My proof: ...
0
votes
2answers
56 views

Bernoulli's inequality by induction

I'm proving Bernoulli's inequality by induction but I noticed something strange. See wikipedia proof: http://en.wikipedia.org/wiki/Bernoulli's_inequality Notice how they multiply both sides of the ...
3
votes
2answers
426 views

Induction: show that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$

The question: show by using induction that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$ My attempt at a solution: The base case $n = 1$ is true. First we use the ...
1
vote
1answer
173 views

Proving by induction that a palindrome contains an even number of $b$s and $c$s

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these ...
2
votes
1answer
223 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question. For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a ...
-1
votes
1answer
72 views

Guess the formula of a matrix

Given a matrix $A$ of size $2\times2$ . $A^2$, $A^3$,$A^4$,and $A^5$ are calculated as seen above. It is required that : Based on your calculation above, Guess a formula for $A^{2n}$ and ...
2
votes
3answers
70 views

Prove $2^n\cdot n! ≤ (n+1)^n$ by induction.

An induction I'm struggling with. Prove $2^n\cdot n! ≤ (n+1)^n$ by induction. An idea was to show that $2^n\cdot n! ≤ 1+n^2$ since $1+n^2 ≤ (n+1)^n$ using Bernoulli. However the inequality is ...
0
votes
3answers
92 views

Induction: show that $\sum\limits_{k=1}^n \frac{k}{2^k} = 2 - \frac{n+2}{2^n}$ for all n $\in Z_+$

So the question in my textbook is: Show by induction that $\sum\limits_{k=1}^n \frac{k}{2^k} = 2 - \frac{n+2}{2^n}$ for all $n$ $\in Z_+$. My attempt at a solution: First of all $Z_+ = 1, 2, 3, 4, ...
7
votes
4answers
424 views

Given that $f(1)= 2013,$ find the value of $f(2013)$?

Suppose that $f$ is a function defined on the set of natural numbers such that $$f(1)+ 2^2f(2)+ 3^2f(3)+...+n^2f(n) = n^3f(n)$$ for all positive integers $n$. Given that $f(1)= 2013$, find the value ...
1
vote
3answers
240 views

Sum of the area of all the rectangles in a rectangular

We have a rectangular shape with the size n × m meters is divided into rectangles of size 1 × 1 meters. Question: Sum of the area of all the rectangles that can be seen in that rectangular is how ...
0
votes
4answers
54 views

I've got a small problem with induction

Let me take a quick example: We want to prove by induction that $3^n-1$ is a multiple of 2, where n is a positive integer. So we start with our "base case" and show that $3^1-1$ is indeed a multiple ...
4
votes
3answers
146 views

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction: How to prove one of them?

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction How to prove one of them ? On Proofwiki there is an article proving the equivalence of the ...
1
vote
2answers
296 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
0
votes
2answers
35 views

Stuck in Induction Inequality

I am doing an inequality induction question that looks like this: Prove that $2^n>3n^2$ for $n\geq 8$ So I have done Step $1,2$ but I can't finish step $3$ Step $1$: RTP: $n=8$ LHS=$2^8=256$ ...
2
votes
2answers
165 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 ...
2
votes
1answer
53 views

proof by induction to fourier problem

So if $h_n (t) = e^{\pi t^2}\frac{d^n}{dt^n}(e^{-2\pi t^2})$. Show proof by induction that $$\widehat{h_n}=(-i)^n h_n$$ Any ideas how to go about with this one? When $n=0 \to \widehat{h_0}=h_0$.
0
votes
1answer
24 views

An inequality related to Stirling Number of the second kind

I want to prove $C_{n,r}^2 \leq C_{n-1,r}C_{n+1,r}$ ($n \geq 2,r \geq 1$) where $C_{n,r}=\dfrac{\binom{n+r+1}{n}(n+r)!}{S_2(n+r,r)r!}$ and $S_2(n,k)$ is the Stirling number of the second kind, ...
1
vote
2answers
69 views

What is wrong with the proof given below?

This problem comes from Solow's book, 2nd edition. What is wrong with the proof given below? If $r$ is a real number with $|r| \leq 1$, then for all integers $n \geq 1, 1 + r + r^2 + \ldots + ...
1
vote
1answer
60 views

Least Element $\implies n\geq 2$ Has Prime Factorization: An Analysis of Strong Induction

$$\color{blue}{\text{PROBLEM}}$$ Show every natural number $n\geq 2$ has a prime factorization. $$\text{TYPICAL SOLUTION}$$ Base case: $2$ is prime, so it is its own prime factorization. ...
1
vote
1answer
40 views

Creating a formula

Let $f :\mathbb{R}\rightarrow\mathbb{R}$ be given by $f(x) = 2x+1$. Find the first $4$ iterates of $x_0 =0$ under $f$. Find a formula for the $n$th iterate $x_n = f^n(0)$. Use induction to prove ...
0
votes
1answer
87 views

Pattern for Recursive Construction

Suppose I have this recursive definition of binary strings. Let $K$ be set of binary strings. The empty string $""$ and $1$ are in $K$. If $k$ is a string in $K$, then so is $0k$, $k0$. And if $k$ is ...
2
votes
4answers
111 views

Stuck while trying to prove $2k^3 \geq (k + 1)^3$…

how can I prove the following: $2k^3 \geq (k + 1)^3$ This is the final part of the elaborate proof for $2^n > n^3 $ give $ n \geq 10$ I have used induction and end up with: $ 2^{K+1} > 2k^3 $ ...
2
votes
6answers
250 views

Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear

It's about proving the following: $$\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ I understand every step in the master solution, however, I have no idea how one can know by intuition to ...
2
votes
2answers
55 views

How come that two inductive subsets can be different

In Enderton's "Mathematical Introduction To Logic". Author says that if we have two operations $f(x,y)$ and $g(x)$ and two sets $B$ and $U$ such that $B \subseteq U$. We say that $S \subseteq U$ is ...
0
votes
1answer
144 views

A problem due to Halmos in Santos' number theory [duplicate]

I found this cool problem in Santos' number theory book, page 12, but he gives the credit to Halmos.Supposedly it must be solved by mathematical induction. Every man in a village knows instantly ...
5
votes
6answers
3k views

Proving $(2n+1) + (2n+3) + \cdots + (4n-1) = 3n^{2}$ for all positive integers $n$

Prove $(2n+1) + (2n+3) + (2n+5) + \cdots + (4n-1) = 3n^{2}$ for all positive integers $n$. So the provided solution avoids induction and makes use of the fact that $1 + 3 + 5 + \cdots + (2n-1) ...
2
votes
4answers
128 views

Proof that $x^k < k^x$

So, I want to prove that $x^k$ is less than $k^x$ for any $x > k$. $x$ and $k$ are both integers. My first approach was an induction over $k$, given that the numbers are integers. I also ...
2
votes
5answers
146 views

Prove the following equality using mathematical induction:

Prove the following equality using mathematical induction: For any integer $n \ge 1$ $$\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$$ I understand for the base base I need to have $n=1$. If I ...
0
votes
1answer
65 views

Proof by induction past exam question attempt

I am revising for an exam that is later today. I'm attempting all questions on past papers. Proof is a topic i've had difficulty with, if someone could check over my answer and give me some ...
0
votes
2answers
40 views

How to prove statement with two variable by induction

I am trying to prove following statement: $[m,n]$ is a set of functions defined as $f \in [m,n] \leftrightarrow f: \{1,...,m\} \rightarrow \{1,...,n\}$. The size of $[m,n]$ is $n^m$ for $m,n \in ...
3
votes
1answer
70 views

Prove $\frac{c_n(a_1,…,a_n)}{c_{n-1}(a_2,…,a_n)}=a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_{n-1}+\frac{1}{a_n}}}}$

For $n>0$ and $a_1,...,a_n \in K$ let $c_n(a_1,...,a_n)$ be the determinant of the matrix $$ \begin{pmatrix} a_1 & 1 & 0 & \cdots & 0 \\ -1 & a_2 & \ddots & ...
1
vote
1answer
24 views

Show by induction, that $\mu(T^{k}A\Delta A)=0~\forall~k\in\mathbb{Z}$

Here are some definitions that might be necessary for my following question: (I) The Quadruple $(\Omega,\mathcal{A},\mu,T)$ is called dynamical system, if $(\Omega,\mathcal{A},\mu)$ is a probability ...
0
votes
1answer
42 views

Proof using induction

I have no clue how to even start this: Proof using induction for every $k=1,2\dots n$ $$\vert\sin\sum_{k=1}^nX_{k}\vert\leq\sum_{k=1}^n\sin X_{k}$$ edit: Sorry, I also know this: $$0\leq ...
0
votes
2answers
50 views

Legality of doubly inductive proof requiring two base cases

I aim to show that the proposition $P_n$: "$11^n - 4^n$ is divisible by $7$" is true for all $n\in\mathbb{N}$. Assume that for some $n \ge 2$, $P_n$ is true. Then since \begin{align} 11^{n+1} - ...
2
votes
1answer
87 views

Prove by induction that $a_{1}+a_{2}+…+a_{n}=\dfrac{(a_{1}+a_{n})n}{2}, \forall n\in \mathbb N$

Prove by induction that $$a_{1}+a_{2}+...+a_{n}=\dfrac{(a_{1}+a_{n})n}{2}, \forall n\in \mathbb N$$ HINT: Supose that: $a_{i+1}-a_{i}= r, \forall i\in \mathbb N$ Let $P(n)$ be the proposition we ...
1
vote
2answers
66 views

How to prove $\sum_{k\leq n}^{n} \binom{n}{k}= 2^n$ by induction [duplicate]

$\sum_{k\leq n}^{n} \binom{n}{k}= 2^n , n, k \in \mathbb{N}$ Im trying with mathematical induction but im stuck. My inductive step: $H) \sum_{k=0}^{h} \binom{h}{k}= 2^h$ $T) \sum_{k=0}^{h+1} ...
1
vote
2answers
101 views

Proof of an inequality by induction[solved]

So I have this inequality and I just can't figure out how to prove it: Prove that ($\forall n\in \mathbb N)$ $$\sum_{k=1}^n \frac{1}{(k+1)\sqrt k}<2.$$ I've figured that for $n=1$ the inequality ...