Tagged Questions

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 ...
9
votes
2answers
370 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 ...
1
vote
1answer
45 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 ...
1
vote
2answers
49 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
2answers
42 views

Formal definition of Mathematical Induction & Strong Induction

I have been reading some notes on Induction and Strong Induction and fully understand how they work. However I was interested in a formal/mathematical way of expressing their definition and was ...
5
votes
2answers
46 views

prove that the greatest number of regions that $n \geq 1$ circles can divide the plane is $n^2-n+2$

This is an induction problem, but I have no idea how to do something like this. Any hints?
4
votes
4answers
94 views

Prove that for every positive integer $n$, $1/1^2+1/2^2+1/3^2+\cdots+1/n^2\le2-1/n$

Base case: n=1. $1/1\le 2-1/1$. So the base case holds. Let $n=k\ge1$ and assume $$1/1^2+1/2^2+1/3^2+\cdots+1/k^2\le 2-1/k$$ We want to prove this for $k+1$, i.e. ...
0
votes
3answers
45 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
2
votes
4answers
115 views

Show that the sum of 2n + 1 consecutive integers is divisible by 2n + 1.

Base case: $n=1$. Picking $2n+1$ random numbers 5,6,7 we get $5+6+7=18$. So, $2(1)+1=3$ which indeed does divide 18. The base case holds. Let $n=k>=1$ and let $2k+1$ be true. We want to show ...
1
vote
3answers
84 views

Prove $(n^5-n)$ is divisible by 5 by induction.

So I started with a base case $n = 1$. This yields $5|0$, which is true since zero is divisible by any non zero number. I let $n = k >= 1$ and let $5|A = (k^5-k)$. Now I want to show $5|B = ...
0
votes
3answers
50 views

Recursive/Fibonacci Induction [duplicate]

1) Let $F_n$ denote the $n^t$$^h$ Fibonacci number. Prove by induction: $$ F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}} $$ Clear ...
0
votes
2answers
67 views

Mathematical Proof Question?

How would prove that this is true for all $k \geq 6$: $$\left(\frac{1+\sqrt{5}}{2}\right)^{k+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k+1} \geq (1.5)^{k} \times \sqrt{5} $$
1
vote
1answer
61 views

How do you write a recursive function in a way that it will be easy to compare it to another while doing a proof by induction?

How would you write the following recursive function in such a way that it will be easy to compare it to another while doing a proof by induction? Base Case: $F(0) = 0; F(1) = 1$. Recursive Step: $ ...
1
vote
2answers
85 views

Can anyone help me understand this Strong Mathematical Induction proof?

I'm not sure if we're allowed to post pictures but I thought it would be easier to read and I didn't see anything in the rules about it. It's question 1. Section 5.4 This question: Here is the ...
2
votes
2answers
71 views

How would you prove $\sum_{i=1}^{n} (3/4^i) < 1$ by induction?

How would you prove this by induction? $\sum_{i=1}^{n} (3/4^i) < 1$, $ \forall n \geq 2$ I can do the base case but dont know how to to finish it
0
votes
1answer
98 views

Induction proof on covering a checkerboard with dominoes - don't think my proof is right.

So I'm trying to solve this problem and I think I'm on the write track, but my proof relies on a domino being divisible by 2, which I don't think is correct. The problem: Prove that a $2^n \times ...
2
votes
2answers
102 views

$ a $ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then $a^n - b^n \leq na^{n-1}(a - b)$.

I'm taking a basic discrete math course and I'm having a hard time with Mathematical Induction. The problem is stated as: Suppose that $ a $ and $b$ are real numbers with $0 < b < a$. Prove ...
4
votes
2answers
94 views

Prove $((n+1)!)^n < 2!\cdot4!\cdots(2n)!$

so I know I need to prove this via induction, but I am somewhat stuck. Here is what I have does so far. Let $p(n) = (n+1)!^n \le 2!\cdot4!\cdot\ldots\cdot(2n)!$ $p(2) = 3!^2\le 2!\cdot4!$ Assume ...
4
votes
2answers
70 views

$\sum_{i=1}^n i\cdot i! = (n+1)!-1$ By Induction

I am trying to prove the following by Mathematical Induction: $$\sum_{i=1}^n i\cdot i! = (n+1)!-1\quad\text{for all integers $n\ge 1$}$$ My proof by Induction follows: First prove $P(1)$ is true, ...
0
votes
0answers
80 views

Proving Vizing's Theorem using Induction

So I would like to prove Vizing's theorem (let d be the maximum degree of any vertex in graph G, any graph can be edge-colored with d or d+1 colors) using induction on the edges of G...here's my ...
0
votes
4answers
77 views

Having a lot of trouble solving this recurrence with iteration and finding a closed form…

I'm learning discrete math and didn't have any trouble with any recurrences in the examples I went over through the chapters on it, but this one problem at the end of the first chapter is killing me, ...
1
vote
1answer
73 views

Mathematical Induction problem- how to show that $P(\bigcup_{i=1}^nA_i)\leq\sum_{i=1}^n P(A_i)$?

Hi I tried doing this problem but im not sure if I am correct can someone help So this what I did Now I am not so sure if this is right
1
vote
2answers
144 views

Basic proof by Mathematical Induction

I am new to proofs and I am trying to learn mathematical induction. I started working out a sample problem, but I am not sure if I am on the right track. I was wondering if someone would be kind ...
4
votes
4answers
124 views

Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$

Prove by Mathematical Induction . . . $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$ I tried solving it, but I got stuck near the end . . . a. Basis Step: $(1)(1!) = (1+1)!-1$ $1 = ...
2
votes
2answers
148 views

Induction Proof: $\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2 $

Prove by Mathematical Induction . . . $$\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2 $$ for all $n \geq 0$ I tried solving it, but I got stuck near the end . . . a. Basis Step: $1\cdot 2^1 ...
7
votes
3answers
234 views

Looking for induction problems that are not formula-based

I am looking for problems that use induction in their proofs such as this one: Given a checker board with one square removed you can cover it with L-shaped pieces made out of three squares. This ...
1
vote
1answer
37 views

Sets induction problem

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
1
vote
1answer
139 views

Proving the sum of the first n natural numbers by induction

I have the Following Proof By Induction Question: $$ (1)(2) + (2)(3) + (3)(4) + \cdots+ (n) (n+1) = \frac{(n)(n+1)(n+2)}{3} $$ Can Anybody Tell Me What I'm Missing. This is where I've Gone So Far. ...
3
votes
4answers
189 views

Proving the sum of the first $n$ natural numbers by induction

I am currently studying proving by induction but I am faced with a problem. I need to solve by induction the following question. $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$ for all $n > 1$. Any ...
0
votes
0answers
111 views

Graph problem - prove by induction

Let's have two sets - $T_1$ and $T_2$ defined as below: Def.1 : $T_1$={ T | T is a tree with at least one edge and T doesn't have vertices from 2 degree } Def.2 : Every connected graph with exactly ...
5
votes
2answers
140 views

Show $ 1 + a + a^2 + a^3 + \ldots + a^n = \frac{a^{n+1}-1}{a-1}$ by induction

How can we show by mathematical induction that the following holds for $ n \ge 0$ and $a \ne 1$? $$ 1 + a + a^2 + a^3 + \ldots + a^n = \frac{a^{n+1}-1}{a-1}$$ I understand the principle of ...
2
votes
3answers
84 views

Can someone intuitively explain the towers of Hanoi and how a proof by induction can be used?

I'm having trouble understanding precisely how the proof by induction is used to show that it takes at most $2^n-1$ moves to get all the disks from one peg to another. Are there any helpful sources ...
1
vote
1answer
234 views

Strong induction proofs

I'm having trouble understanding strong induction proofs I understand how to do ordinary induction proofs and I understand that strong induction proofs are the same as ordinary with the exception ...
1
vote
5answers
181 views

Need help with simple proof by mathematical induction

$$ \sum_{k=1}^n k^4 = {(6n^5+15n^4+10n^3-n) \over 30} $$ How can this be proven using mathematical induction? My teacher isn't any help, he just tells me to think about it, but I've read the textbook ...
0
votes
1answer
85 views

Using induction to show a greedy algorithm always makes the optimal task selection

Suppose we have a greedy algorithm like the following: ...
0
votes
2answers
79 views

How can induction be used to prove binary search is correct?

I'm having trouble understanding how to find an invariant to check if it's preserved, and generally how induction is used in proving the correctness of algorithms (binary search primarily, but others ...
0
votes
1answer
51 views

Integers and Induction Question (formula for Fibonacci numbers)

I've been working on this for a while now and I can't seem to get anywhere. Could anyone help me out or walk me through a solution? Any help at all would be wonderful. Thank you. Find a, b such that ...
1
vote
2answers
104 views

Induction problem? (ratio of consecutive Fibonacci numbers)

Define $a_1 = 1$ and for all natural $n$'s, $a_{n+1} = 1 + \dfrac{1}{a_n}$. Prove that for every natural $n$, $$a_n = \dfrac{F_{n+1}}{F_n}.$$ I'm not sure if this is an induction problem or not, but ...
0
votes
2answers
62 views

Discrete Math problem

I believe this is an induction problem. Let $a, b$ be positive integers with $a < b$. Prove that for any natural number $n$, $a^n < b^n$. I feel I should start with a base case $n = 1$ which ...
1
vote
4answers
244 views

Proof by Induction: $\sum_0^nx^i=(1-x^{n+1})/(1-x)$

I'm trying to do my Maths assignment but I can't get this done. I can do other questions but this one is different. This is a picture of the question. My usual first step is to proof it when n = 1. ...
1
vote
2answers
35 views

How does this prove that P(k) of every k is true?

This is an example from my textbook. I'm very rusty with simplifying algebraic expression so i hope you'll forgive me for that. The textbook says there are two rules to Mathematical Induction: 1) We ...
1
vote
3answers
137 views

Prove that $\bigcap\limits_{i = 1}^n {\left( {{A_i} - B} \right)} = \bigcap\limits_{i = 1}^n {{A_i}} - B$

Prove that if $A_1, A_2, \ldots , A_n$ and $B$ are sets, then $$(A_1 − B) \cap (A_2 − B) \cap \cdots \cap (A_n − B) = (A_1 \cap A_2 \cap \cdots \cap A_n) − B.$$
1
vote
2answers
106 views

Prove the $3^n < n!$ for all $n > 6$

I'm trying to use induction to prove this. I'm sure it's a simple proof, but I can't seem to get over the first few steps. Any help? Allow $P(n)=3^n<n!$ Base Case: $P(7) = 3^7<7! ...
1
vote
1answer
57 views

Help with induction - For $n > 1$ a natural number $n-1$ is also a natural number.

The problem I am stuck on is this one: If $n>1$ is a natural number then $n-1$ is also a natural number. I am told to use induction. Normally I would just do the following: My statement is ...
15
votes
3answers
398 views

A (probably trivial) Induction Problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some ...
3
votes
1answer
139 views

inequality with sum of powers

How to prove the following inequality: $$\forall n\geqslant 4:\dfrac {3^{n}+4^{n}+\cdots +\left( n+2\right) ^{n}} {\left( n+3\right) ^{n}} < 1$$
6
votes
1answer
229 views

Backwards induction to show that $x_1\cdots x_n \leq ((x_1+\cdots+x_n)/n )^n$

This question is from "Concrete Mathematics", by Knuth. Sometimes it's possible to use induction backwards, proving things from $n$ to $n-1$ instead of vice versa! For example, consider the ...
3
votes
1answer
534 views

(Inductive Proofs) Show why one inductive hypothesis works, and the other does not.

Here's a homework problem I have for my class about Discrete Mathematics: Suppose that we want to prove that $$\frac12\cdot\frac34\cdot\ldots\cdot\frac{2n-1}{2n} < \frac1{\sqrt{3n}}$$ ...
0
votes
3answers
137 views

How does one prove that the number $111\ldots 1$ (formed by $3^{n}$ digits all equal to $1$) is divisible by $3^{n}?$

I am self-studying Discrete Mathematics (in Portuguese), and there is one exercise I was not able to solve. Show that the number $111\ldots 1$ (formed by $3^{n}$ digits are equal to $1$) is ...

1 2