Tagged Questions

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

2
votes
2answers
366 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
113 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
190 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
77 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
189 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 ...
0
votes
0answers
114 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
73 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
78 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
52 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
49 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
108 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
95 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
49 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
80 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
155 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
38 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
150 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
1answer
419 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
93 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
47 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 ...
3
votes
2answers
110 views

Proving $r!$ divides the product of r succesive positive integers

I have to prove the following theorem: Prove that the product of $r$ consecutive positive integers in divisible by $r!$ I am having a hard time getting a generalization down for the full set of ...
0
votes
1answer
131 views

Strong Induction Base Case

Is a base case needed ? In response to many questions on this subject I offer the clarification below.
2
votes
3answers
105 views

For $n \geq 2$, prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})…(1- \frac{1}{n^2}) = \frac{n+1}{2n}$

For $n \geq 2$ prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$ We need to use induction. The Principle of Mathematical Induction, Theorem 4.2.1, ...
1
vote
2answers
79 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
1
vote
0answers
27 views

There are 10 non distinguishable balls and one of these has different weight

There are 10 non distinguishable balls and one of these has different weight(one does not know whether it is weigh more or less than others). One can use scales 3 times to compare their weight. You ...
1
vote
3answers
52 views

Simple induction proof

Im having a lot of trouble proving by induction that $3^n + 5^n \geq 2^{n+2}.$ The base step is easy, but I don't seem to find the way to proof the inductive step.
1
vote
4answers
297 views

Proof that the number of diagonals of a polygon is $\frac{n(n-3)}{2} $

For $n \geq 3$ proof that the number of diagonals of a polygon is $\frac{n(n-3)}{2} $ using induction. I don't know how to start this problem, can you give me a hint?
1
vote
1answer
29 views

Proof $\prod_{i = 1}^n \frac{n + i}{2i-3} = 2^n(1-2n)$ using inducction

i'm trying to solve this, using induction. The base step is easy, there's no difficult there. The problem comes in the inductive step, I got to demonstrate that: $$\prod_{i = 1}^{n+1} \frac{n+ 1 + ...
1
vote
1answer
30 views

Is induction starting at $n=0$ on $F[x_1,\dots,x_n]$ correct?

Suppose you have some polynomial ring $F[x_1,\dots,x_n]$ and you want to prove some fact about it by induction on the number of formal variables $x_i$. Is it ever wrong to start with $n=0$? Since ...
0
votes
2answers
36 views

solve by induction

$$\sum_{r=2}^n{1\over r^2-1}=\frac34-{2n+1\over 2n(n+1)}$$ after I got to $n=k+1$ and tried to get both sides equal I got stuck, prove: $n=k+1$ ; $${1\over k^2 -1} + {1\over (k+1)^2 -1}=\frac34 - ...
2
votes
2answers
49 views

How to prove by induction

How to prove by induction? For $n\ge 1$: $\sum_{j=n}^{2n-1} (1/j) = \sum_{k=1}^{2n-1} ((-1)^{k+1}/k)$ 1) Base case $\sum_{j=1}^{1} (1/j) = 1 = \sum_{k=1}^{1} ((-1)^{k+1}/k)$ 2) Induction [Prove ...
2
votes
3answers
49 views

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$ I've plugged $3$ in for $n$ I get $7 \le 8$ then I set $2(n+1) +1 \le 2^{n+1}$ then I'm lost.
0
votes
2answers
56 views

Proving the geometric sum formula by induction

$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$ I want to prove this by induction. Here's what I have. $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$ I wanted to factor a ...
1
vote
2answers
57 views

Sum from $k=1$ to $n$ of $k^3$

$$\sum_{k=1}^n k^3 = \left(\frac{1}{2}n(n+1) \right)^2$$ I want to prove this using induction. I start with $(\frac{n}{2}(n+1))^2 + (n+1)^3$ and rewrite $(n+1)^3$ as $(n+1)(n+1)^2$, then factor out ...
1
vote
4answers
85 views

Proof for maths induction

prove: $$ \sum_{r=1}^{n}[r^{2}+1](r!)=n[(n+1)!]$$ for all $n \in N$ prove $n=1$, $(1^2+1)(1!)$ = $1[(1+1)!]$ assume true for $n=k$, $(k^2+1)$$(k!)$= $k$$[(k+1)!]$ I got to here : ...
0
votes
0answers
28 views

Validity of a proof by induction

By intuition, I would say that if L1 is a subset of L and that L is regular, then L1 is also regular, because L1 has less states than L2 and therefore there must be an automata for L1 too. However, ...
0
votes
1answer
27 views

Induction with two indexes

I want to prove that if $G$ is a group and $a\in G$, $n,m\in \Bbb Z$, then $a^na^m=a^{n+m}$. I think, that it's easier to prove the case when $n,m\in \Bbb N$. I found this question: Induction (over 2 ...
1
vote
2answers
86 views

proof by maths induction

not sure how to prove this: for all positive intergers prove: \begin{equation} 1+2(2)+3(2^2)+...+n(2^{n-1})=(n-1)(2^n)+1 \end{equation} heres my try: prove $n=1$ : \begin{equation} 1=1 ...
0
votes
1answer
41 views

Proving some sequence of integers by induction

Say I have a sequence like: $0,1,2,0,1,2,0,1,2,\dots$ in other words $1=0$, next $2=1$, third $3=2$ etc. and a formula that I believe works for my sequence. How would I prove that the sequence works ...
0
votes
1answer
72 views

An inequality by induction

I am reading Arthur Engel's Problem Solving Strategies. Section 8. The Induction Principle Problem 24 with its solution are attached . I do not understand the second inequality in the solution on ...
3
votes
1answer
153 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
0
votes
2answers
54 views

Show that $2^n < n!$ for every positive integer $n$ with $n\geq 4$. [duplicate]

Using Mathematical induction prove the above proposition. Basis step can be verified easily. But how can i show that it is true for $p(n+1)$.
0
votes
2answers
124 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
-2
votes
3answers
68 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) + ...
2
votes
2answers
359 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
367 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
51 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
63 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 ...
2
votes
2answers
258 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
324 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 ...