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 meant ...

learn more… | top users | synonyms

-2
votes
3answers
87 views

Induction proof to find formula

I ran into some problem when I am doing some review. I need to find the formula for the following by exploring the cases n = 1,2,3,4 and prove by induction I have this sequence $$a_n = 1/(1*2) + ...
3
votes
2answers
877 views

Base cases in strong induction

In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption. Why then, in some other cases, is it ...
2
votes
6answers
413 views

If $a_1,\ldots,a_n>0$ and $a_1+\cdots+a_n<\frac{1}{2}$, then $(1+a_1)\cdots(1+a_n)<2$.

Assume that $a_1,a_2,\ldots,a_n>0$ and $a_1+a_2+\cdots+a_n<\frac{1}{2}$, and prove that $$(1+a_1)(1+a_2)\cdots(1+a_n)<2$$ I've tried Hölder's inequality (the same result can easily be ...
1
vote
2answers
65 views

How can I come up with a formula for this summation?

I have to come up with a formula for: $$\sum_{0\le i\le n\text{, i is even}}^\ i^2$$ and then prove it by using induction. I know how to do the proof, but I am stuck on coming up with the formula. I ...
0
votes
1answer
75 views

Prove by induction.

I'm working on an assignment and stuck on the same question for the last three hours. I have no idea how I'm suppose to factor and prove this question by induction. Use mathematical induction on ...
3
votes
2answers
394 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
421 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
25 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 ...
0
votes
3answers
57 views

How to show $((k+1)!)^2 2^k \leq (2(k+1))!$

How do you show that $((k+1)!)^2 2^{k+1} \leq (2(k+1))!$ This is part of an induction proof and I have not made any progress.
2
votes
1answer
219 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
49 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
127 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 = ...
0
votes
1answer
53 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
4answers
870 views

Mathematical Induction (summation): $\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$

I am stuck on this question from the IB Cambridge HL math text book about Mathematical induction. I am sorry about the bad formatting I am new and have no idea how to write the summation sign. Using ...
1
vote
1answer
135 views

Properties of Natural Numbers and Mathematical Induction

When working with natural numbers how to check that the property we consider is "permissible" to speak about? And not like the property "The smallest positive integer not definable in under eleven ...
2
votes
0answers
85 views

Induction: Show: $\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times … \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}}$ [duplicate]

The question: Show by using induction that: $\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times ... \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}}$ for all $n$ $\in$ $Z_+$ My attempt at a ...
0
votes
1answer
44 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
57 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
68 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
564 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
289 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
368 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
vote
2answers
139 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 = \\ ...
-1
votes
1answer
85 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
73 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
97 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, ...
0
votes
1answer
174 views

What is mutual induction and how does that differ from regular induction?

http://web.cecs.pdx.edu/~black/CS311/proof_by_mutual_induction.pdf I read this and I fail to see any difference. It's the same thing, prove for n = 0 and then prove for n = k+1.
0
votes
4answers
56 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 ...
1
vote
2answers
418 views

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

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 ...
4
votes
3answers
265 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 ...
0
votes
2answers
49 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
1answer
60 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$.
1
vote
2answers
78 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 + ...
0
votes
1answer
49 views

How Can I find the summation of divisors of $n^p$.

For Example $n=8$ and $p=2$. So $n^p=64$. And the summation of divisors is $1+2+4+8+16+32+64=127$. But the problem arises when $n=10^6$ and $p=10^6$. Remember u can modulus the result by $100$.
1
vote
1answer
62 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
42 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 ...
2
votes
4answers
120 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 $ ...
0
votes
1answer
91 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
2answers
56 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 ...
2
votes
5answers
212 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 ...
2
votes
4answers
132 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 ...
0
votes
1answer
89 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
48 views

Prove by induction on two variables that there are $n^m$ functions from $\{1, \ldots m\}$ to $\{1, \ldots, n\}$

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 ...
1
vote
1answer
26 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 ...
3
votes
1answer
75 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 & ...
0
votes
1answer
44 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 ...
1
vote
1answer
80 views

Prove any $k\in\mathbb{N}$ can be created using sum of $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$

I need to prove that any integer can created using a sum of elements in $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$ without repetition. My attempt was just bad... I've ...
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} - ...
1
vote
2answers
63 views

Induction proof equivalence

In Induction, we do the following: Check $P(1)$ is true, then show that if $P(k)$ is true, then $P(k+1)$ is also true. So we proceed to assuming $P(k)$ is true, then attempt to show $P(k+1)$ is true, ...
2
votes
2answers
73 views

Prove by induction that $P_{n}<2^{2^{n}}$, being $P_{n}$ the $n^{th}$ prime number

Prove by induction that $P_{n}<2^{2^n}$, been $P_n$ the $n^\text{th}$ prime number The prime numbers´s set is defined as $\mathbb P:= \left \{2,3,5,7,11,\ldots\right\} $ Let $P(n)$ be the ...