Question

. For any integer n ≥ 2, let A(n) denote the number of ways to fully parenthesize a sum of n terms such as a1 + · · · + an. Examples:

• A(2) = 1, since the only way to fully parenthesize a1 + a2 is (a1 + a2).

• A(3) = 2, since the only ways to fully parenthesize a1 + a2 +
a3 are ((a1 + a2) + a3) and

(a1 + (a2 + a3)).

• A(4) = 5, since a1 + a2 + a3 + a4 can be parenthesized as ((a1
+ a2) + (a3 +

a4)), (((a1 + a2) + a3) + a4), (a1 + (a2 + (a3 + a4))), ((a1 + (a2
+ a3)) + a4), and (a1 +

((a2 + a3) + a4)).

Prove using complete induction that A(n) <= (n 1)n−1 for all integers

n >= 2. Your proof does not need to be formal, but it should have a clear structure and be easy to understand.

Answer #1

There is an error in the question in the expression A(n)

I have provided the correct expression and solved it by induction

Let n be an integer, with n ≥ 2. Prove by contradiction that if
n is not a prime number, then n is divisible by an integer x with 1
< x ≤√n.
[Note: An integer m is divisible by another integer n if there
exists a third integer k such that m = nk. This is just a formal
way of saying that m is divisible by n if m n is an integer.]

Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3 for n>=
3.
Let P(n) denote an an <= 2^n.
Prove that P(n) for n>= 0 using strong induction:
(a) (1 point) Show that P(0), P(1), and P(2) are true, which
completes
the base case.
(b) Inductive Step:
i. (1 point) What is your inductive hypothesis?
ii. (1 point) What are you trying to prove?
iii. (2 points) Complete the proof:

Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3 for n>=
3.
Let P(n) denote an an <= 2^n.
Prove that P(n) for n>= 0 using strong induction:
(a) (1 point) Show that P(0), P(1), and P(2) are true, which
completes
the base case.
(b) Inductive Step:
i. (1 point) What is your inductive hypothesis?
ii. (1 point) What are you trying to prove?
iii. (2 points) Complete the proof:

Prove that there is no positive integer n so that 25 < n^2
< 36. Prove this by directly proving the negation.Your proof
must only use integers, inequalities and elementary logic. You may
use that inequalities are preserved by adding a number on both
sides,or by multiplying both sides by a positive number. You cannot
use the square root function. Do not write a proof by
contradiction.

How many ways are there to represent a positive integer n as a
sum of (a) k non-negative integers? (b) k positive integers? Note:
the order of summation matters. For example, take n = 3, k = 2.
Then the possible sums in (a) are 3+0, 2+1, 1+2, 0+3

Let
a1, a2, ..., an be distinct n (≥ 2) integers. Consider the
polynomial
f(x) = (x−a1)(x−a2)···(x−an)−1 in Q[x]
(1) Prove that if then f(x) = g(x)h(x)
for some g(x), h(x) ∈ Z[x],
g(ai) + h(ai) = 0 for all i = 1, 2, ..., n
(2) Prove that f(x) is irreducible over Q

1. Prove that an integer a is divisible by 5 if and only if a2
is divisible by 5.
2. Deduce that 98765432 is not a perfect square. Hint: You can use
any theorem/proposition or whatever was proved in class.
3. Prove that for all integers n,a,b and c, if n | (a−b) and n |
(b−c) then n | (a−c).
4. Prove that for any two consecutive integers, n and n + 1 we
have that gcd(n,n + 1)...

Let n ≥ 1 be an integer. Use the Pigeonhole Principle to prove
that in any set of n + 1 integers from {1, 2, . . . , 2n}, there
are two elements that are consecutive (i.e., differ by one).

Let n be a positive integer, and let Hn denote the graph whose
vertex set is the set of all n-tuples with coordinates in {0, 1},
such that vertices u and v are adjacent if and only if they differ
in one position. For example, if n = 3, then (0, 0, 1) and (0, 1,
1) are adjacent, but (0, 0, 0) and (0, 1, 1) are not. Answer the
following with brief justification (formal proofs not
necessary):
a....

Let A = (A1, A2, A3,.....Ai) be defined as a sequence containing
positive and negative integer numbers.
A substring is defined as (An, An+1,.....Am) where 1 <= n
< m <= i.
Now, the weight of the substring is the sum of all its
elements.
Showing your algorithms and proper working:
1) Does there exist a substring with no weight or zero
weight?
2) Please list the substring which contains the maximum weight
found in the sequence.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 3 minutes ago

asked 33 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago