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

0
votes
2answers
43 views

Math Induction to prove recursion

This is a problem from a practice test. I don't understand how the answer was produced using math induction. And yes, math induction is required for this problem. Define a function f: $\mathbb{N}$ ...
2
votes
2answers
89 views

Can someone help me with this proof?

Prove that $$1^2-2^2+3^2...+(-1)^{n-1}n^2=(-1)^{n-1}\frac{n(n+1)}{2}$$ whenever $n$ is a positive integer. I used $2$ as my base case and it worked. Then I plugged in $k$ for $n$. Now I can't figure ...
1
vote
6answers
245 views

Prove that ${n^5 - n}$ is divisible by 5 [duplicate]

I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it. I am trying to prove it for several hours now, I started with ${n^5 - n} \mod 5 = 0$ but then I ...
0
votes
3answers
62 views

Induction problem: “if the group has at least one player who is better than Messi, then all the members of the group are better than Messi”

I'm having some trouble with the following problem: "A french man is trying to prove that any non empty group of french soccer players satisfies the following: 'if the group has at least one player ...
1
vote
1answer
35 views

Is it obvious that $\sum_n x_n = 0 $ when $x_n = 0 ~ \forall n \in \mathbb N$?

Until recently I used to think that because of induction, a statement $P_n$ which is true $\forall n \in \mathbb N$ was also true when $n \to \infty$. Life was simple, and I was happy. Then someone ...
2
votes
2answers
168 views

Got stuck in proving monotonic increasing of a recurrence sequence

I'm stuck with the prove of the following recurrence sequence which was part of and old exam. $a_1:=\frac{1}{2}, a_{n+1}:=a_n(2-a_n)$ for $n \in \mathbb{N}$ I have to show that $0 <a_n < 1$ ...
0
votes
2answers
99 views

Proof by Induction - Sequence of integers

Suppose a sequence of integers $a_1$, $a_2$, ... is defined as: $$a_1 = 3$$ $$a_2 = 6$$ $$a_n = 5a_{n-1} - 6a_{n-2} + 2$$ for all $n\ge3$ $\mathbf {Prove}$ $\mathbf {S(n)}$: $a_n = 1 + 2^{n-1} + ...
0
votes
2answers
58 views

proof by strong induction of single variable with exponent

$x^n + \frac{1}{x^n} \in \mathbb{Z}$ (is an integer), for all positive integers $n$, where $x$ is rational. I've surmised that the only rational numbers that satisfy $x$ are 1 and -1. Thus, as you ...
0
votes
1answer
46 views

Prove that $n^2 < 2^n$ for all $n \geq 6$

My approach to solving this: By induction. (1) $S(n) = (n^2 < 2^n)$ for all $n \geq 6$, $n \in \mathbb N$. (2) Base Case: $n = 6$ $$6^2 < 2^6$$ $$36 < 64$$ So the statement is true for ...
1
vote
2answers
158 views

Strong Induction: Finding the Inductive Hypothesis

Consider this claim: Every positive integer greater than 29 can be written as a sum of a non-negative multiple of 8 and a non-negative multiple of 5. Assume you are in the inductive step and trying ...
0
votes
1answer
89 views

Permuation, disjoint cycles proof by induction.

I am having a hard time writing out a general proof. Can anyone please help? Thank you. Exercise: Show that any k-cycle (a1,......,ak) can be written as a product of some number of (k-1) 2-cycles. ...
3
votes
2answers
85 views

If I'm asked to prove that $n \le m$, is it sufficient to show that $n < m$?

I have a homework question, which is to prove by induction that $\sum\limits_{r=1}^{n} \frac{1}{\sqrt{r}} \leq 2\sqrt{n}$ for every integer $n \geq 1$. I've managed to show by induction that ...
0
votes
2answers
58 views

Induction with multiple variables

Let the function g : R $\rightarrow$ R satisfy $g(xy) = x \cdot g(y) +y \cdot g(x)$ for all real numbers x and y. Prove $g(u^n) = nu^{n-1}g(u)$, for all positive integers $n$ and all real numbers ...
0
votes
1answer
70 views

Induction proof of function from $\mathbb R$ to $\mathbb R$

Let f be a function from $\mathbb R$ to $\mathbb R$ satisfying $f(\frac{x_1+x_2}{2})=\frac{f(x_1)+f(x_2)}{2}$ Prove that for any positive integer $n$ we have ...
2
votes
1answer
53 views

Prove GM-AM inequality using induction

Show that $G_{2^n}\le A_{2^n}$ by using induction on n. I've proven the base case in the previous exercise: Let $G_2=\sqrt{a_1a_2}$ and $A_2=\frac{1}{2}(a_1+a_2)$ and $a_1,a_2 \in \mathbb{R}$ ...
-4
votes
2answers
190 views

Induction of $A_i$ [duplicate]

The base case $n=1$: $B\cup\left(\bigcap_{i=1}^1A_i\right)=B\cup A_1$ and $\bigcap_{i=1}^1(B\cup A_i)=B\cup A_1$. Now, suppose inductively that ...
-1
votes
2answers
57 views

Discrete Math: Ways to Prove Induction

The point of mathematical induction is to prove $\forall x\geq b[P(x)]$ by instead proving $P(b)\wedge \forall x\geq b[P(x)\rightarrow P(x+1)]$ ($b$ is often, but not always, $0$ or $1$). However, ...
2
votes
2answers
92 views

PROVE if $x \ge-1 $then $ (1+x)^n \ge 1+nx $ , Every $n \ge 1$

Use mathematical induction to prove this. Here is my answer but I stuck at certain point. Base Case: n=1 $$(1+x)^1 \ge 1+x $$ True , Induction Case: n=k assume $$(1+x)^k ...
-1
votes
2answers
197 views

Proof by induction that $B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$

$\displaystyle B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$ I was able to prove this without using induction, however I am supposed to prove it using induction. How should I go about ...
0
votes
1answer
27 views

Proving by induction propositions of the type $P(n_1, n_2, …, n_k)$, where $n_1, n_2, …,$ and $n_k$ are natural numbers

For example: I've seen proofs of the multinomial theorem that use induction in the number of terms that are elevated at some power, but none that use induction in the exponent instead of using it in ...
1
vote
1answer
400 views

Proof by induction involving fibonacci numbers

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims: (i) For each $n≥0$, $f_{3n}$ is even. (ii) For each ...
3
votes
4answers
138 views

Prove that the inequality $(1+ \frac{1}{n})^n < n$ holds for all $n \geq 3$

First we need to prove the basis. If we let $n=3$, then $(1+ \frac{1}{3})^3 < 3$ $(\frac{3}{3}+ \frac{1}{3})^3 < 3$ $(\frac{4}{3})^3 < 3$ $(\frac{64}{27}) < 3$ The inequality ...
0
votes
3answers
366 views

Strong Induction and Recursion

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that ...
0
votes
1answer
47 views

Tangent equation divisible by (x-y)

I have attempted this proof but I am not sure is the induction step is correct any assistance would be appreciated also I am not sure if i have proved what I was trying to. Let ...
1
vote
1answer
50 views

Splitting up bracket terms

I found a statement saying: Let $\circledast $ be an associative binary operation on a set $\mathbb{X}$. A bracket term of length n, consisting of n elements $a_1, ..., a_n$ and arbitrary brackets, ...
1
vote
3answers
94 views

Prove by induction: If $h$ and $k$ are any two distinct integers, then $h^n-k^n$ is divisible by $h-k$.

If $h$ and $k$ are any two distinct integers, then $h^n-k^n$ is divisible by $h-k$. Let's start with the basis. Let $n=1$, then $h^1-k^1 = h-k$ Now for the induction, I can't use $k$ because I ...
1
vote
2answers
139 views

Using induction, prove that $(-7)^n -9^n$ is divisible by $16$

First of all, I think the problem should be $(-7)^n -9^n$ is divisible by $-16$ because if I test the basis by letting $n=1$, I have $-16$ instead of $16$. Edit: Alright ... I sort of understand why ...
1
vote
3answers
89 views

Using Induction, prove that $107^n-97^n$ is divisible by $10$

Using Induction, prove that $107^n-97^n$ is divisible by $10$ We need to prove the basis first, so let $ n = 1 $ $107^1-97^1$ $107-97 = 10$ This statement is clearly true when $ n = 1 $ Now ...
1
vote
0answers
89 views

Show $0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}$ by induction

Show that if $0\leq x < n, n \geq 1$, and $n\in\mathbb{N}$ then $$ 0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}. $$ By using induction. Progress: Decided to split ...
1
vote
1answer
41 views

Small question about inductive proof about rational sequences

I am writing an inductive proof about this: the description is not terribly important so you don't have to read that. here's my question: let $P(n)$ be the statement that $x_n$ is a rational ...
2
votes
2answers
718 views

Show that $e^x > 1 + x + x^2/2! + \cdots + x^k/k!$ for $n \geq 0$, $x > 0$ by induction

Show that if $n \geq 0$ and $x>0$, then $$ e^x > 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}.$$ Not sure where to get started with this induction proof.
2
votes
2answers
155 views

show that $2n\choose n$ is divisible by 2 [duplicate]

I tried using induction, but in the inductive step, I get: If $2n\choose n$ is divisible then I want to see that $2n +2\choose n +1$ $${2n +2\choose n +1} = (2n + 2)!/(n+1)!(n +1)! = {2n\choose n} ...
0
votes
2answers
297 views

Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves?

The Tower of Hanoi game consists of three identical upright pegs and n rings all of different diameters that can be stacked over any of the pegs. Initially, all of the rings are stacked around one of ...
0
votes
1answer
125 views

Using induction to prove a general form from a recurrence relation

I have the recurrence relation: $a_{n+2} = \dfrac{-a_{n}}{(n+2)(n+1)}$. I have done some work to identify that two cases emerge: one is n is positive, and one if n is negative. If n = 2m (even) ...
5
votes
2answers
208 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
1
vote
0answers
129 views

Two very difficult induction proofs; having trouble with the inductive step

$$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+1}\frac{n-2k-1}{k+1} = n-2 + \frac{1}{n+1}\binom{2n}{n}$$ $$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+2}\frac{n-2k-1}{k+1} = -n + ...
3
votes
2answers
76 views

Prove by induction $a-b|a^{n}-b^{n}$ for $n\in\mathbb N$

$P(1)$: $a-b|a-b$ $P(n) \Rightarrow P(n+1)$: $a-b|a^{n}-b^{n}\Rightarrow a-b|a^{n+1}-b^{n+1}$ I'm not sure how to proceed from here. Any help is appreciated.
0
votes
1answer
90 views

Mathematical Induction Recursion

Consider the recursion given by $f(n) = 2f(n−1)− f(n−2)+6$ for $n ≥ 2$ with $f (0) = 2$ and $f (1) = 4.$ Use mathematical induction to prove that $f (n) = 3n^2 −n+2$ for all integers $n ≥ 0.$
1
vote
2answers
56 views

$2^n-1 = \sum_{j<n}2^j$ induction explanation

I am having trouble understanding the following analysis after we arrived to the conclusion: $2^k - \sum_{j=0}^{j=k-1}2^j = 1$ after arriving to the conclusion, they say, I think to explain that the ...
1
vote
3answers
53 views

Prove by induction that $99 | 10^{2n} + 197$ for $n\ge 1$

I'm not sure whether I should make use of the transitive property, or this $a|b\Rightarrow b = a*z$ / $z\in\mathbb Z$ to solve the problem. I'm mainly looking to solve it through induction using the ...
1
vote
2answers
215 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
4
votes
2answers
105 views

Counting tilings of a $2\times n$ board

Let $n=>1$ be an integer and consider a $2*n$ board $B_n$ consisting of $2n$ cells,each one having sides of length one. This picture shows $B_{13}$: For $n=>1$, let $a_n$ be the number of ...
1
vote
1answer
51 views

Induction: $\frac{n!}{x(x+1)\cdots(x+n)} = \binom{n}{0}\frac{1}{x}-\binom{n}{1}\frac{1}{x+1}+\cdots+(-1)^n\binom{n}{n}\frac{1}{x+n}$

$$\frac{n!}{x(x+1)\cdots(x+n)} = \binom{n}{0}\frac{1}{x}-\binom{n}{1}\frac{1}{x+1}+\cdots+(-1)^n\binom{n}{n}\frac{1}{x+n}, \quad \text{for } x \not \in \{0,-1,-2,\dots,-n\}$$ Can somebody please help ...
2
votes
1answer
83 views

Help with Elementary number theory please

Use the second principle of finite induction to establish that for all $n\geq1$ : $$a^n-1=(a-1)\left(a^{n-1}+a^{n-2}+a^{n-3}+\cdots+a+1\right) $$ Step by step explanation please! I'm confused how the ...
2
votes
2answers
157 views

Proving strings [duplicate]

We consider strings of n characters, each character being a, b, c, or d, that contain an even number of as. (0 is even.) Let $E_n$ be the number of such strings.Prove that for any integer $n ...
0
votes
1answer
39 views

Prove that $n! > 2^n$ for $n\geq 4$ (solution question)

I'm having a hard time figuring out a part of the solution So I'm trying to prove $n! > 2^n$ for $n \geq 4$ and the solution is attached as a picture I'm confused as to what happens from the ...
3
votes
4answers
152 views

Proving that $4n^2 - 1$ is divisible by 3.

I apologise (apologize for my American friends :)) if I have overlooked something simple which I am sure is the case. Unnecessary background: This came up when trying to prove a related assertion ...
0
votes
2answers
1k views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
0
votes
0answers
199 views

The Toad and Frog Game - Proof by Inducation

Toads and Frogs is played on a 1 × n strip of squares. At any time, each square is either empty or occupied by a single toad or frog. Although the game may start at any configuration, it is customary ...
0
votes
1answer
58 views

Proof by pumping lemma

Let's say that we have to prove that $L = \{ww^Rv |w,v\in \Sigma^*\}$ is irregular. I would take a string such that $w = baba^m$ and $w^R=a^mbab$ and $v = a$ and then I would pump divide $w$ into ...